强连通分量的应用，详见《挑战程序设计》P324
模板（2019.7）：
namespace two_sat { int dfn[M*2], low[M*2], cnt, stk[M*2], top, cmp[M*2], tot, n; bool vis[M*2]; vector<int> g[M*2]; void init(int sz) { n = sz; } void add(int u, int v) { g[u].pb(v); } void tarjan(int u) { dfn[u] = low[u] = ++cnt; stk[++top] = u; vis[u] = true; for (int v : g[u]) { if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if(vis[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]) { cmp[u] = ++tot; while(stk[top] != u) cmp[stk[top]] = tot, vis[stk[top--]] = false; vis[stk[top--]] = false; } } bool ck() { for (int i = 1; i <= 2*n; ++i) if(!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++i) { if(cmp[i] == cmp[i+n]) return false; } return true; } }
思路：强连通分量分解，看有没有两个同一个国家的代表在一个强连通分量里，如果有，就是NIE。这个不是关键，关键是怎么输出，输出还要用一下dfs，把所有能到达的点标记一下，顺便判断一下和之前有没有矛盾，有矛盾的话所有被标记的点又要重新标记回去。其实这道题可以不用强连通分量分解，直接dfs。
代码1（强连通分量分解+dfs）：
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) int n,m,u,v; const int N=2e4+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; bool vis1[N]; int cmp[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } void init() { for(int i=0;i<=2*n;i++)g[i].clear(),rg[i].clear(); } bool DFS(int u) { vis[u]=true; vis1[u]=true; if(vis[u^1])return false; for(int i=0;i<g[u].size();i++) { if(!vis[g[u][i]]&&!DFS(g[u][i]))return false; } return true; } void red(int u) { vis1[u]=false; vis[u]=false; for(int i=0;i<g[u].size();i++) { if(vis1[g[u][i]])red(g[u][i]); } } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin>>n>>m) { init(); for(int i=0;i<m;i++) { cin>>u>>v; u--; v--; add_edge(u,v^1); add_edge(v,u^1); } int t=scc(); bool flag=false; for(int i=0;i<2*n;i+=2)if(cmp[i]==cmp[i+1]){cout<<"NIE"<<endl;flag=true;break;} if(flag)continue; mem(vis,false); mem(vis1,false); for(int i=0;i<2*n;i+=2) { if(vis[i]) { cout<<i+1<<endl; continue; } else if(vis[i+1]) { cout<<i+2<<endl; continue; } else { if(DFS(i)) { cout<<i+1<<endl; } else { red(i); cout<<i+2<<endl; DFS(i+1); } } } } return 0; }
代码2（dfs）:
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) int n,m,u,v,tot; const int N=2e4+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; int cmp[N]; int s[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } /*void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; }*/ void init() { for(int i=0;i<=2*n;i++)g[i].clear(),rg[i].clear(); } bool DFS(int u) { if(vis[u^1])return false; if(vis[u])return true; vis[u]=true; s[tot++]=u; for(int i=0;i<g[u].size();i++) { if(!DFS(g[u][i]))return false; } return true; } bool solve() { mem(vis,false); for(int i=0;i<2*n;i+=2) { if(vis[i]||vis[i^1])continue; tot=0; if(!DFS(i)) { while(tot)vis[s[--tot]]=false; if(!DFS(i^1))return false; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin>>n>>m) { init(); for(int i=0;i<m;i++) { cin>>u>>v; u--; v--; add_edge(u,v^1); add_edge(v,u^1); } //int t=scc(); if(solve()) { for(int i=0;i<2*n;i++) if(vis[i])cout<<i+1<<endl; } else cout<<"NIE"<<endl; } return 0; }
例题2：POJ 3207 Ikki's Story IV - Panda's Trick
思路：由于题目说每个点最多只能连一次，所以我直接用起点的坐标映射成它在圆内，+n后映射成它在圆外。不过这样求强连通时就要遍历每个点了，有点慢。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=2e3+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; vector<int>s; bool vis[N]; int cmp[N]; int n,m,u,v; int a[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); int k=0; mem(vis,false); for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } int main() { ios::sync_with_stdio(false); cin.tie(0); mem(a,-1); cin>>n>>m; for(int i=0;i<m;i++) { cin>>u>>v; a[u]=v; a[v]=u; s.pb(u); s.pb(v); } sort(s.begin(),s.end()); for(int i=0;i<s.size();i++) { for(int j=i+1;j<s.size();j++) { int l=min(s[i],a[s[i]]),r=max(s[i],a[s[i]]); int _l=min(s[j],a[s[j]]),_r=max(s[j],a[s[j]]); if((r>_l&&r<_r&&l<_l)||(l<_r&&l>_l&&r>_r)) { add_edge(s[i],s[j]+n); add_edge(s[j],s[i]+n); add_edge(s[i]+n,s[j]); add_edge(s[j]+n,s[i]); } } } int t=scc(); for(int i=0;i<s.size();i++) if(cmp[s[i]]==cmp[s[i]+n]) { cout<<"the evil panda is lying again"<<endl; return 0; } cout<<"panda is telling the truth..."<<endl; return 0; }
例题3：POJ 3683 Priest John's Busiest Day
思路：大白书上的是输出拓扑序大的，不懂，留坑。
补坑：拓扑序大的没有边连向拓扑序小的强联通，所以不会产生矛盾。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=2e3+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; int cmp[N]; int n,m,u,v; int S[N],T[N],D[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); int k=0; mem(vis,false); for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } void init() { for(int i=0;i<=n;i++)g[i].clear(),rg[i].clear(); } void solve() { mem(vis,false); } int main() { int a,b,c,d; while(~scanf("%d",&n)) { init(); for(int i=0;i<n;i++) { scanf("%d:%d %d:%d %d",&a,&b,&c,&d,&D[i]); S[i]=a*60+b; T[i]=c*60+d; } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(min(S[i]+D[i],S[j]+D[j])>max(S[i],S[j]))add_edge(i,n+j),add_edge(j,n+i); if(min(T[i],T[j])>max(T[i]-D[i],T[j]-D[j]))add_edge(n+j,i),add_edge(n+i,j); if(min(T[i],S[j]+D[j])>max(T[i]-D[i],S[j]))add_edge(n+i,n+j),add_edge(j,i); if(min(T[j],S[i]+D[i])>max(T[j]-D[j],S[i]))add_edge(i,j),add_edge(n+j,n+i); } } int t=scc(); bool flag=false; for(int i=0;i<n;i++)if(cmp[i]==cmp[i+n]){ flag=true; break; } if(flag)printf("NO "); else { printf("YES "); for(int i=0;i<n;i++) { if(cmp[i]>cmp[n+i]) printf("%02d:%02d %02d:%02d ",S[i]/60,S[i]%60,(S[i]+D[i])/60,(S[i]+D[i])%60); else printf("%02d:%02d %02d:%02d ",(T[i]-D[i])/60,(T[i]-D[i])%60,T[i]/60,T[i]%60); } } } return 0; }
思路：一开始看起来很复杂，其实只要建好边就好了。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=2e3+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; vector<int>s; bool vis[N]; int cmp[N]; int n,m,u,v; int a[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); int k=0; mem(vis,false); for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } void init() { for(int i=0;i<=2*n;i++)g[i].clear(),rg[i].clear(); } int main() { ios::sync_with_stdio(false); cin.tie(0); int a; string t; while(cin>>n>>m) { for(int i=0;i<m;i++) { cin>>u>>v>>a>>t; if(t[0]=='A') { if(a==1) { add_edge(u,v); add_edge(v,u); add_edge(u+n,u); add_edge(v+n,v); } else { add_edge(u,v+n); add_edge(v,u+n); } } else if(t[0]=='O') { if(a==1) { add_edge(u+n,v); add_edge(v+n,u); } else { add_edge(u+n,v+n); add_edge(v+n,u+n); add_edge(u,u+n); add_edge(v,v+n); } } else if(t[0]=='X') { if(a==1) { add_edge(u,v+n); add_edge(v,u+n); add_edge(v+n,u); add_edge(u+n,v); } else { add_edge(u,v); add_edge(v,u); add_edge(v+n,u+n); add_edge(u+n,v+n); } } } scc(); bool flag=false; for(int i=0;i<n;i++) if(cmp[i]==cmp[i+n]){ flag=true; break; } if(flag)cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }
例题5：POJ 3648 Wedding
思路：与例1相同，不过要建一条0号新娘和他新郎的边，这样只会选出新郎那一边的人。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=200; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; int cmp[N]; int s[N]; int n,m,u,v; int tot=0; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } void init() { for(int i=0;i<=2*n;i++)g[i].clear(),rg[i].clear(); } bool DFS(int u) { if(u<n&&vis[u+n])return false; if(u>=n&&vis[u-n])return false; if(vis[u])return true; vis[u]=true; s[tot++]=u; for(int i=0;i<g[u].size();i++) { if(!DFS(g[u][i]))return false; } return true; } bool solve() { mem(vis,false); for(int i=0;i<2*n;i++) { if(vis[i])continue; if(i>=n&&vis[i-n])continue; if(i<n&&vis[i+n])continue; tot=0; if(!DFS(i)) { while(tot)vis[s[--tot]]=false; if(i<n&&!DFS(i+n))return false; if(i>=n&&!DFS(i-n))return false; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); string s1,s2; while(cin>>n>>m) { if(n==0&&m==0)break; init(); for(int i=0;i<m;i++) { cin>>s1>>s2; int t=0; for(int j=0;j<s1.size();j++) { if('0'<=s1[j]&&s1[j]<='9')t=t*10+s1[j]-'0'; else { if(s1[j]=='w') { u=t; } else { u=n+t; } } } t=0; for(int j=0;j<s2.size();j++) { if('0'<=s2[j]&&s2[j]<='9')t=t*10+s2[j]-'0'; else { if(s2[j]=='w') { v=t; } else { v=n+t; } } } if(v<n)add_edge(u,v+n); else add_edge(u,v-n); if(u<n)add_edge(v,u+n); else add_edge(v,u-n); } add_edge(0,n); int t=scc(); bool flag=false; for(int i=1;i<n;i++) { if(cmp[i]==cmp[i+n]) { flag=true; break; } } if(flag) { cout<<"bad luck"<<endl; } else { tot=0; mem(vis,false); solve(); for(int i=1;i<n;i++) { if(vis[i])cout<<i<<"h"; else cout<<i<<"w"; if(i!=n-1)cout<<' '; } cout<<endl; } } return 0; }
例题6：Codeforces 468B - Two Sets
思路：如果x在a集合中，那么a-x不存在的话，x一定在b集合（x在a==>x在b）；如果a-x存在，那么有(原命题：x在a==>a-x在a，逆否命题：a-x在b==>x在b)，同理，x在b集合中也是一样的。建边建好了就可以输出拓扑序大的了。
代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=2e5+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; int belong[N]={0}; bool vis[N]; int cmp[N]; int s[N]; int n; int tot=0; struct node { int v,id; bool operator < (node t)const { return v<t.v; } }a[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=0;i<2*n;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } /*bool DFS(int u) { if(u<n&&vis[u+n])return false; if(u>=n&&vis[u-n])return false; if(vis[u])return true; vis[u]=true; s[tot++]=u; for(int i=0;i<g[u].size();i++) { if(!DFS(g[u][i]))return false; } return true; } bool solve() { mem(vis,false); for(int i=0;i<2*n;i++) { if(vis[i])continue; if(i>=n&&vis[i-n])continue; if(i<n&&vis[i+n])continue; tot=0; if(!DFS(i)) { while(tot)vis[s[--tot]]=false; if(i<n&&!DFS(i+n))return false; if(i>=n&&!DFS(i-n))return false; } } return true; } */ int main() { ios::sync_with_stdio(false); cin.tie(0); int A,B; cin>>n>>A>>B; for(int i=0;i<n;i++)cin>>a[i].v,a[i].id=i; sort(a,a+n); for(int i=0;i<n;i++) { //bool flag=false; int t=lower_bound(a,a+n,node{A-a[i].v,0})-a; if(t!=n&&a[t].v==A-a[i].v) { //flag=true; add_edge(a[i].id,a[t].id); add_edge(a[t].id+n,a[i].id+n); } else { add_edge(a[i].id,a[i].id+n); } t=lower_bound(a,a+n,node{B-a[i].v,0})-a; if(t!=n&&a[t].v==B-a[i].v) { //flag=true; add_edge(a[i].id+n,a[t].id+n); add_edge(a[t].id,a[i].id); } else { add_edge(a[i].id+n,a[i].id); } /*if(!flag) { cout<<"NO"<<endl; return 0; }*/ } int t=scc(); for(int i=0;i<n;i++) if(cmp[i]==cmp[i+n]) { cout<<"NO"<<endl; return 0; } cout<<"YES"<<endl; //solve(); for(int i=0;i<n;i++)if(cmp[i]>cmp[i+n])cout<<0<<' ';else cout<<1<<' '; cout<<endl; return 0; }
代码复杂了，因为所有数不同，所以数可以直接映射成下标。
例题7：Codeforces 867E National Property
思路：学会建矛盾边（自己的叫法）。
代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=2e5+5; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; vector<int>a[N]; bool vis[N]; int cmp[N]; int n,m; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=1;i<=2*m;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } void init() { for(int i=0;i<=2*m;i++)g[i].clear(),rg[i].clear(); for(int i=0;i<n;i++)a[i].clear(); } int main() { ios::sync_with_stdio(false); cin.tie(0); int t,b; while(cin>>n>>m) { init(); for(int i=0;i<n;i++) { cin>>t; for(int j=0;j<t;j++)cin>>b,a[i].pb(b); } bool f=false; for(int i=0;i<n-1;i++) { //cout<<a[i].size()<<endl; if(a[i].size()<=a[i+1].size()) { for(int j=0;j<a[i].size();j++) { if(a[i][j]<a[i+1][j]) { add_edge(a[i][j],a[i+1][j]); add_edge(a[i+1][j]+m,a[i][j]+m); break; } else if(a[i][j]>a[i+1][j]) { add_edge(a[i][j],a[i][j]+m); add_edge(a[i+1][j]+m,a[i+1][j]); add_edge(a[i][j]+m,a[i+1][j]); add_edge(a[i+1][j],a[i][j]+m); break; } } } else { bool flag=false; for(int j=0;j<a[i+1].size();j++) { if(a[i][j]<a[i+1][j]) { flag=true; add_edge(a[i][j],a[i+1][j]); add_edge(a[i+1][j]+m,a[i][j]+m); break; } else if(a[i][j]>a[i+1][j]) { flag=true; add_edge(a[i][j],a[i][j]+m); add_edge(a[i+1][j]+m,a[i+1][j]); add_edge(a[i][j]+m,a[i+1][j]); add_edge(a[i+1][j],a[i][j]+m); break; } } if(!flag) { f=true; break; } } } if(f)cout<<"No"<<endl; else { //cout<<1<<endl; scc(); for(int i=1;i<=m;i++) { if(cmp[i]==cmp[i+m]) { f=true; // cout<<i<<endl; break; } } if(f)cout<<"No"<<endl; else { cout<<"Yes"<<endl; int cnt=0; for(int i=1;i<=m;i++) if(cmp[i]<cmp[i+m])cnt++; cout<<cnt<<endl; for(int i=1;i<=m;i++)if(cmp[i]<cmp[i+m])cout<<i<<' '; cout<<endl; } } } return 0; }
总结：
关于建边：如果x一定不能选，那么建一条x连向！x的边。
关于输出：2-sat问题的输出如果没有限制条件，那么直接输出拓扑序大的一组答案，如果有限制条件，DFS染色标记后再输出答案。