强连通分量的应用，详见《挑战程序设计》P324

例题1：

思路：强连通分量分解，看有没有两个同一个国家的代表在一个强连通分量里，如果有，就是NIE。这个不是关键，关键是怎么输出，输出还要用一下dfs，把所有能到达的点标记一下，顺便判断一下和之前有没有矛盾，有矛盾的话所有被标记的点又要重新标记回去。其实这道题可以不用强连通分量分解，直接dfs。

代码1（强连通分量分解+dfs）：

#include
      
       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
       
        g[N];vector
        
         rg[N];vector
         
          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
          
           =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
           
            >n>>m) { init(); for(int i=0;i
            
             >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"<
            
           
          
         
        
       
      

代码2（dfs）:

#include
      
       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
       
        g[N];vector
        
         rg[N];vector
         
          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
          
           =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
           
            >n>>m) { init(); for(int i=0;i
            
             >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<
             
              <
             
            
           
          
         
        
       
      

例题2：

思路：由于题目说每个点最多只能连一次，所以我直接用起点的坐标映射成它在圆内，+n后映射成它在圆外。不过这样求强连通时就要遍历每个点了，有点慢。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
             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
            
             g[N];vector
             
              rg[N];vector
              
               vs;vector
               
                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
                
                 =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
                 
                  >u>>v; a[u]=v; a[v]=u; s.pb(u); s.pb(v); } sort(s.begin(),s.end()); for(int i=0;i
                  
                   _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
                  
                 
                
               
              
             
            
           
          
         
        
       
      

例题3：

思路：大白书上的是输出拓扑序大的，不懂，留坑。

补坑：拓扑序大的没有边连向拓扑序小的强联通，所以不会产生矛盾。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
             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
            
             g[N];vector
             
              rg[N];vector
              
               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
               
                =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
                
                 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
                 
                  cmp[n+i]) printf("%02d:%02d %02d:%02d\n",S[i]/60,S[i]%60,(S[i]+D[i])/60,(S[i]+D[i])%60); else printf("%02d:%02d %02d:%02d\n",(T[i]-D[i])/60,(T[i]-D[i])%60,T[i]/60,T[i]%60); } } } return 0;}
                 
                
               
              
             
            
           
          
         
        
       
      

例题4：

思路：一开始看起来很复杂，其实只要建好边就好了。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
             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
            
             g[N];vector
             
              rg[N];vector
              
               vs;vector
               
                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
                
                 =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
                 
                  >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
                 
                
               
              
             
            
           
          
         
        
       
      

例题5：

思路：与例1相同，不过要建一条0号新娘和他新郎的边，这样只会选出新郎那一边的人。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            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
            
             g[N];vector
             
              rg[N];vector
              
               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
               
                =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(vis[u])return true; vis[u]=true; s[tot++]=u; for(int i=0;i
                 
                  =n&&vis[i-n])continue; 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
                   
                    >s1>>s2; int t=0; for(int j=0;j
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

例题6：

思路：如果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
      
       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
       
        g[N];vector
        
         rg[N];vector
         
          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
          
           =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(vis[u])return true; vis[u]=true; s[tot++]=u; for(int i=0;i
            
             =n&&vis[i-n])continue; 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
              
               >a[i].v,a[i].id=i; sort(a,a+n); for(int i=0;i
               
                cmp[i+n])cout<<0<<' ';else cout<<1<<' '; cout<
               
              
             
            
           
          
         
        
       
      

代码复杂了，因为所有数不同，所以数可以直接映射成下标。

例题7：

思路：学会建矛盾边（自己的叫法）。

代码：

#include
      
       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
       
        g[N];vector
        
         rg[N];vector
         
          vs;vector
          
           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
           
            =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>>m) { init(); for(int i=0;i
             
              >t; for(int j=0;j
              
               >b,a[i].pb(b); } bool f=false; for(int i=0;i
               
                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][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"<
                
               
              
             
            
           
          
         
        
       
      

总结：

关于建边：如果x一定不能选，那么建一条x连向！x的边。

关于输出：2-sat问题的输出如果没有限制条件，那么直接输出拓扑序大的一组答案，如果有限制条件，DFS染色标记后再输出答案。