https://ac.nowcoder.com/acm/contest/327/F

C++版本一

std

題解： 2-sat 圖論

#include <bits/stdc++.h> using namespace std; #define ll long longconst int MAXN = 400010; const int MAXM = 800010; struct Edge {int to,next; }edge[MAXM]; int head[MAXN],tot; void init() {tot = 0;memset(head,-1,sizeof(head)); } void addedge(int u,int v) {edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN]; int Index,top; int scc; bool Instack[MAXN]; int num[MAXN];void Tarjan(int u) {int v;Low[u] = DFN[u] = ++Index;Stack[top++] = u;Instack[u] = true;for(int i = head[u];i != -1;i = edge[i].next){v = edge[i].to;if( !DFN[v] ){Tarjan(v);if(Low[u] > Low[v])Low[u] = Low[v];}else if(Instack[v] && Low[u] > DFN[v])Low[u] = DFN[v];}if(Low[u] == DFN[u]){scc++;do{v = Stack[--top];Instack[v] = false;Belong[v] = scc;num[scc]++;}while(v != u);} }bool solvable(int n) {memset(DFN,0,sizeof(DFN));memset(Instack,false,sizeof(Instack));memset(num,0,sizeof(num));Index = scc = top = 0;for(int i = 0;i < n;i++)if(!DFN[i])Tarjan(i);for(int i = 0;i < n;i += 2){if(Belong[i] == Belong[i^1])return false;}return true; }int n,m; int a[200005]; vector<int> v[200005];int main() {scanf("%d%d",&n,&m);init();for (int i=1;i<=n;i++){scanf("%d",&a[i]);}for (int i=0;i<m;i++){int k;scanf("%d",&k);for (int j=1;j<=k;j++){int x;scanf("%d",&x);v[x].push_back(i);}}for (int i=1;i<=n;i++){if (v[i].size()==2){if (a[i]==1){int x=v[i][0]<<1;int y=v[i][1]<<1;addedge(x,y^1);addedge(x^1,y);addedge(y,x^1);addedge(y^1,x);}else{int x=v[i][0]<<1;int y=v[i][1]<<1;addedge(x,y);addedge(x^1,y^1);addedge(y,x);addedge(y^1,x^1);}}else if (v[i].size()==1){if (a[i]==1){int x=v[i][0]<<1;addedge(x,x^1);}else{int x=v[i][0]<<1;addedge(x^1,x);}}else if (v[i].size()==0){if (a[i]==1){addedge(0,0);addedge(1,1);}}}if (solvable(m<<1)) puts("YES");else puts("NO");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的处女座与宝藏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。