cf776 D 并查集

题目大意就是有n个门，m个机关，机关对应的是k个门，点击机关m则k个门的状态全部反转。询问是否存在一种方式让所有门都变为1；每个门都是只有两个机关可影响到他。

分析一下问题可以知道，对于门初始为1，则这个门对应的两个机关只能一起选，或者都不选，也就是这两个机关是被绑定着的。
对于门初始为0，则这个们对应的两个机关只能选一个，选了A就不能选B，选B,就不能选A；
考虑机关只有选与不选对不对。我们这么去假设，设置种类并查集pre[i]和pre[i + m],pre[i]指的是i的同类，pre[i + m]是指i的敌对面。对于上面的每个机关，我们都可以对应的去连线。
（1）对于门i为1，t1,t2为两个与门i有关联的门。t1与t2去合并，t1+m与t2+m去合并，(t1与t2是同类，t1的对立面也就是t2的对立面)
（2）对于门i为0，t1,t2为两个与门i有关联的门。t1与t2+m去合并，t1 + m与t2去合并，这样就表明了他们的敌对关系。
怎么判断no呢？就是上面的（1）（2）出现矛盾的时候就直接NO；比如你t1要和t2是敌对，但是最后的结果表名他们是同类，则直接NO；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define ll long long
#define double long double
using namespace std;
#define PI 3.1415926535898
#define eqs 1e-10
const long long max_ = 1e5 + 7;
int mod = 10000;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
int pre[max_ * 3];
int get(int x) {
	if (pre[x] == x)return x;
	return pre[x] = get(pre[x]);
}
int n, m,sta[max_];
vector<int> switch_[max_];
vector<int> no[max_];
void hb(int a, int b) {
	int t1 = get(a), t2 = get(b);
	if(t1 != t2)pre[t1] = t2;
}
signed main() {
	n = read(), m = read();
	for (int i = 1; i <= 2 * m; i++) {pre[i] = i;}
	for (int i = 1; i <= n; i++) {
		sta[i] = read();
	}
	for (int i = 1; i <= m; i++) {
		int num = read();
		while (num--){
			int t = read(); switch_[i].push_back(t);
			no[t].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (sta[i]) {
			//按两次
			hb(no[i][0], no[i][1]);
			hb(no[i][0] + m, no[i][1] + m);
		}
		else {
			//按一次
			hb(no[i][0], no[i][1] + m);
			hb(no[i][0] + m, no[i][1]);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!sta[i]) {
			//按一次
			int t1 = get(no[i][0]), t2 = get(no[i][1]);
			if (t1 == t2) {
				cout << "NO\n"; return 0;
			}
		}
	}
	cout << "YES\n";
	return 0;
}