一家旅馆的n间不同的房间里困住了n个人，其中有些房间是被锁住了，有些房间是打开的，但是只有在所有房间同时打开的情况下，被困人员才能逃离。现在有m个开关，每个开关控制着一些房间的门，开关的作用是使得这些房间原来开着的关上，关上的打开，但每个门都被两个开关控制。
[输入格式]
第一行，有两个正整数n和m（2 ≤n,m ≤ 10^5），n表示房间的数量，m表示开关的数量。第二行n个数，表示每个房间的状态，0表示房间是锁住的，1表示房间是开着的。
再接下来m行，每行第一个数x表示第i把锁控制的房间数，再接着有x个数，分别表示所控制的房间编号（1~n）。
数据保证每个房间是被两个开关控制的。
[输出格式]
如果房间都能被打开则输出“YES”，否则输出“NO”
输入样例#1：
33
输出样例#1：
NO
输入样例#2：
33
12
输出样例#2：
YES
输入样例#3：
33
13
输出样例#3：
NO
由于每个门只会被两个钥匙控制，那么两个钥匙的选或不选就能建立起一种对应关系。即如果门本来是开着的，那么用了一把必须用另一把，不用一把必须不用另一把；如果们本来是开着的，那么不用一把必须用另一把，用了一把必须不用另一把。
#includeusingnamespacestd;constintmaxn=5e5+5;intlow[maxn],dfn[maxn];inthead[maxn],tot,scc[maxn];intn,m,Index,ins[maxn],cnt;inta[maxn];stackst;structEdge{intu,v,next;}edge[maxn<<1];vectorvec[maxn];voidinit{memset(head,-1,sizeof(head));tot=1;}voidadd(intu,intv){edge[++tot].u=u;edge[tot].v=v;edge[tot].next=head[u];head[u]=tot;}voidtarjan(intu){low[u]=dfn[u]=++Index;ins[u]=1;st.push(u);for(inti=head[u];i!=-1;i=edge[i].next){intto=edge[i].v;if(!dfn[to]){tarjan(to);low[u]=min(low[u],low[to]);}elseif(ins[to]){low[u]=min(low[u],dfn[to]);}}if(low[u]==dfn[u]){++cnt;intv;do{v=st.top;ins[v]=0;st.pop;scc[v]=cnt;}while(v!=u);}}intsat{for(inti=1;i<=m;i++){if(scc[i]==scc[i+m]){returnfalse;}}returntrue;}intmain{init;intx,y;cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=m;i++){cin>>y;for(intj=1;j<=y;j++){cin>>x;vec[x].push_back(i);}}for(inti=1;i<=n;i++){intu=vec[i][0],v=vec[i][1];if(a[i]){//如果门本来是开着的，则选择了一把，就必须选择另外一把add(u,v);add(v,u);add(u+m,v+m);add(v+m,u+m);}else{//如果门本来是关着的，着选择了一把，就不能选择另外一把add(u,v+m);add(v+m,u);add(u+m,v);add(v,u+m);}}for(inti=1;i<=2*m;i++){if(!dfn[i]){tarjan(i);}}if(sat){cout<<"Yes"<
以上就是小编为大家整理的关于《luogu CF776D The Door Problem（2-sat问题）》的最新内容，了解更影视资讯、明星动态，请多关注新开传奇最大网站。
