题目链接

题意

\(n\)人进行\(m\)场比赛，给定\(m\)场比赛的双方编号；再给定已知的为\(good\ player\)的\(x\)个人的编号，已知的为\(bad\ player\)的\(y\)个人的编号。准则是每场比赛的两个选手必定一位来自\(good\ player\)，另一位来自\(bad\ player\). 问是否可以据此将所有选手划分成两个阵营.

思路

// 题意和样例都很迷...

总的来说就是二分图染色，已经染好了若干个点，问能否顺利染成一个二分图。

但是不允许有孤立点。

具体操作上用\(dfs\)比较方便，因为图不连通，并查集不太好处理。

Code

#include <bits/stdc++.h>

#define maxn 2010

#define maxm 10010

bool flag;

int c[maxn], tot, ne[maxn], n, m, a, b, cnt;

struct Edge {

    int to, ne;

    Edge(int _to=0, int _ne=0): to(_to), ne(_ne) {}

}edge[maxm<<1];

void add(int u, int v) {

    edge[tot] = Edge(v, ne[u]);

    ne[u] = tot++;

}

using namespace std;

typedef long long LL;

void dfs(int u, int col) {

    ++cnt;

    if (flag) return;

    c[u] = col;

    for (int i = ne[u]; ~i; i = edge[i].ne) {

        int v = edge[i].to;

        if (c[v]==-1) dfs(v, !col);

        else if (c[v] == col) { flag = true; return; }

    }

}

void work() {

    int x, y;

    tot = 0; memset(ne, -1, sizeof(ne)); memset(c, -1, sizeof c);

    for (int i = 0; i < m; ++i) {

        scanf("%d%d", &x, &y);

        add(x, y), add(y, x);

    }

    for (int i = 0; i < a; ++i) scanf("%d", &x), c[x] = 0;

    for (int i = 0; i < b; ++i) scanf("%d", &x), c[x] = 1;

    flag = false;

    for (int i = 1; i <= n; ++i) {

        if (c[i] != -1) dfs(i, c[i]);

        if (flag) { printf("NO\n"); return; }

    }

    for (int i = 1; i <= n; ++i) {

        if (c[i] == -1) cnt = 0, dfs(i, 0);

        if (flag || cnt == 1) { printf("NO\n"); return; }

    }

    printf("YES\n");

}

int main() {

    while (scanf("%d%d%d%d", &n, &m, &a, &b) != EOF) work();

    return 0;

}