HDU-5971

题目链接：传送门

题目大意：

    给出 $n$ 个人，$m$ 场 比赛 $x$ 个已经确定的好人 $y$ 个已经确定的坏人。     每场比赛都由 好人和坏人 组成。     问是否能够将每个人划分成好人或者坏人。

解题思路：

    这里介绍用并查集的思想     num_i表示i与其父亲之间的关系，king_i表示i自己的种类     后面确认好（坏）人的时候，若这个人已经确定了是好人，则判断这个人的状态和数组中对应的状态是否相同

    最后、出现矛盾有以下种情况： $①$ 合并时发现祖先相同却属于同一种人 $②$ 确认好（坏）人时这个人的属性相反 $③$ 确定这个人是好人时，这个人在数组中的状态与之前的矛盾 $④$ 与$③$相反 $⑤$ n个人没有全部访问

代码思路：

    因为这里保存的是相互关系，所以合并的时候应该相互异或并异或1     找祖先的时候很定也是相互异或     在给出某个人的属性的时候，若他的祖先没有属性，则要用这个人的属性与祖先的状态（数组中的值）共同影响得出祖先的属性，即作异或处理

核心：并查集的花式使用，同时使用二分图染色应该简单一点

#include<bits/stdc++.h> using namespace std; const int N = 2005; int f[N], num[N], vis[N], kind[N]; int n, m, u, v, x, y, temp, conf; int find(int x) { if(x != f[x]) { int fa = f[x]; f[x] = find(f[x]); num[x] = num[x] ^ num[fa]; } return f[x]; } void init(int n) { conf = 1; for(int i=0 ; i<=n; i++) { f[i] = i; num[i] = vis[i] = 0; kind[i] = -1; } } int main() { while(~scanf("%d%d%d%d", &n, &m, &x, &y)) { init(n); for(int i=0; i<m; i++) { scanf("%d%d", &u, &v); int fa = find(u), fb = find(v); if(fa == fb) { if(num[u] == num[v]) conf = 0; } else { f[fb] = fa; num[fb] = num[v] ^ num[u] ^ 1; } vis[u] = vis[v] = 1; } for(int i=0; i<x; i++) { scanf("%d", &temp); vis[temp] = 1; if(kind[temp]==1) conf = 0; kind[temp] = 0; int fx = find(temp); if(kind[fx]>=0) conf = conf && (kind[temp]^num[temp]==kind[fx]); else kind[fx] = kind[temp]^num[temp]; } for(int i=0; i<y; i++) { scanf("%d", &temp); vis[temp] = 1; if(kind[temp]==0) conf = 0; kind[temp] = 1; int fx = find(temp); if(kind[fx]>=0) conf = conf && (kind[temp]^num[temp]==kind[fx]); else kind[fx] = kind[temp]^num[temp]; } for(int i=1; i<=n; i++) conf = conf && vis[i]; if(conf) puts("YES"); else puts("NO"); } }