题目描述
处女座进行了一次探险，发现了一批宝藏。如果他获得这批宝藏，那么他一辈子都不需要工作了。但是处女座遇到了一个难题。

宝藏被装在n个宝箱里，宝箱编号为1,2,…,n，只有所有宝箱在某一时间被打开，处女座才能获得宝藏。有m个开关，每个开关控制k个宝箱，如果按下一个开关，那么这k个宝箱的开关状态都会发生改变（从开启变成关闭，从关闭变成开启），处女座想知道他能否获得这批宝藏。

输入描述:
第一行两个正整数n,m，
第二行n个整数，每个整数为0或1，表示初始时宝箱的状态，0表示开启，1表示关闭
接下来m行，每行开头一个整数k表示这个开关控制的宝箱的个数，接下来k个整数，表示控制宝箱的编号
1<=n,m<=200000
1<=k<=n
题目保证每个宝箱最多被两个开关控制。

输出描述:
一行，如果处女座能获得宝藏，输出”YES”，否则输出”NO”
示例1
输入
复制
4 4
1 0 1 1
2 3 4
2 1 3
1 2
2 1 2
输出
复制
YES

对于每一个开关我们只有按或者不按，也就是0或1的选择。

不难看出是一道2-SAT,的问题。

然后我们分别按照要求建边即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=4e5+10,M=2e6+10;
int n,m,k,dfn[N],low[N],col[N],co,cnt,a[N],vis[N];
int head[N],nex[M],to[M],tot;
vector<int> v[N]; stack<int> st;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void tarjan(int x){
	dfn[x]=low[x]=++cnt; vis[x]=1; st.push(x);
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]); low[x]=min(low[x],low[to[i]]);
		}else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
	}
	if(dfn[x]==low[x]){
		int u; co++;
		do{
			u=st.top(); vis[u]=0; st.pop(); col[u]=co;
		}while(u!=x);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1,k,x;i<=m;i++){
		scanf("%d",&k);
		while(k--){
			scanf("%d",&x);	v[x].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(v[i].size()==2){
			if(!a[i]){
				add(v[i][0],v[i][1]),add(v[i][1],v[i][0]);
				add(v[i][0]+m,v[i][1]+m),add(v[i][1]+m,v[i][0]+m);
			}else{
				add(v[i][0],v[i][1]+m),add(v[i][1],v[i][0]+m);
				add(v[i][0]+m,v[i][1]),add(v[i][1]+m,v[i][0]);
			}
		}else if(v[i].size()==1){
			if(!a[i]){
				add(v[i][0],v[i][0]+m);
			}else{
				add(v[i][0]+m,v[i][0]);
			}
		}else if(v[i].size()==0){
			if(a[i])	return puts("NO"),0;
		}
	}
	for(int i=1;i<=m*2;i++)	if(!dfn[i])	tarjan(i);
	for(int i=1;i<=m;i++)	if(col[i]==col[i+m])	return puts("NO"),0;
	puts("YES");
	return 0;
}