[图算法之强连通分量，两种算法]--[POJ 2186 Popular Cows]

骑猪看日落 2021-09-28 10:06 346阅读 0赞

### 图算法之强连通分量 ###

*  前言
 *  Kosaraju算法
 *   *  例子：
 *  Tarjan算法

# 前言 #

本节介绍求图中有向图强连通分量，以及各个顶点分属于哪个强连通分量的方法。  
主要有两种算法：Kosaraju, Tarjan

# Kosaraju算法 #

参考书籍：算法概论、算法竞赛入门经典训练指南  
思想：深度优先搜索(DFS)、强连通分量、有向无环图（DAG）、源点（入读为0的点）、汇点（出度为0的点）、反转图（原图中所有方向取反的图）

假设:

V 1 − > V 2 − > V 3 − > . . . − > V n V^1->V^2->V^3->...->V^n V1−>V2−>V3−>...−>Vn 表示强连通分量之间的连接关系  
 V i V^i Vi:一个强连通分量的顶点集合，可以看成是新生成的点  
上面这个连接关系生成新的连接关系，即一个DAG图。

Kosaraju算法首先要找到第一个强连通分量 V 1 V^1 V1中的一个点，然后对反转图  G R G^R GR进行DFS搜索，这次DFS搜索到的顶点均属于同一个连通分量 V 1 V^1 V1,然后对 V 2 V^\{2\} V2中的点在 G R G^R GR中进行DFS，此时DFS到的点属于 V 2 V^\{2\} V2，以此类推即可找到所有强连通分量，以及每个顶点所对应的强连通分量

代码：

vector<int> G[maxn], G2[maxn]; //G是原图，G2是反转图
    vector<int> S;
    int vis[maxn],sccno[maxn];
    int scc_cnt;//强连通分量的标号;
    
    void dfs1(int u){ 
    	if(vis[u]) return ;
    	vis[u]=1;
    	for(int i=0;i<G[u].size();i++) dfs1(G[u][i]);
    	S.push_back(u); //最后被push进去的是源点或者说是V1里的点
    }
    
    void dfs2(int u){ 
    	if(sccno[u]) return;
    	sccno[u]=scc_cnt;
    	for(int i=0;i<G2[u].size();i++) dfs2(G2[u][i]);
    }
    
    void find_scc(int n){ 
    	scc_cnt=0; //初始化强连通分量
    	S.clear(); 
    	memset(sccno,0,sizeof(sccno)); 
    	memset(vis,0,sizeof(vis));
    	for(int i=0;i<n;i++) 
    		df1(i); //第一遍遍历生成S
    	for(int i=n-1;i>=0;i--)
    		//如果该点还未归入任何强连通分量的话
    		if(!sccno[S[i]]) { 
    			scc_cnt++; //强连通分量的标号加加
    			dfs2(S[i]);
    	}
    }
    //最后的结果就是sccno数组里的各个顶点的值代表了所属的强连通分量。

## 例子： ##

[POJ-2186-Popular Cows][]

有一个坑是下标是从1开始的，所以要注意。

代码：

#include<iostream>
    #include<string.h>
    #include<vector>
    
    #define MAX 10010
    using namespace std;
    
    vector<int> g[MAX],gr[MAX];
    int n,m; //n为总的牛数，m为数对的个数 
    int sccnum; //强连通分量的标号 
    int scc[MAX];
    
    vector<int> s; //逆序存放各个强连通分量的点 
    bool is_visited[MAX];
    
    void dfs1(int index){ 
    	is_visited[index]=true;
    	
    	int size=g[index].size();
    	
    	for(int i=0;i<size;i++){ 
    		int temp_index=g[index][i];
    		if(!is_visited[temp_index]){ 
    			dfs1(temp_index);
    		}
    	}
    	s.push_back(index);
    }
    
    void dfs2(int index){ 
    	scc[index]=sccnum;
    	
    	int size=gr[index].size();
    	
    	for(int i=0;i<size;i++){ 
    		int temp_index=gr[index][i];
    		
    		if(!scc[temp_index]){ 
    			dfs2(temp_index);
    		}
    	}
    }
    
    
    int main(){ 
    	int a,b;
    	while(cin>>n>>m){ 
    		memset(is_visited,0,sizeof(is_visited));
    		sccnum=0;
    		memset(scc,0,sizeof(scc));
    		 
    		s.clear();
    		for(int i=1;i<=n;i++){ 
    			g[i].clear();
    			gr[i].clear();
    		}//清空图 
    		
    		for(int i=0;i<m;i++){ 
    			cin>>a>>b;
    			g[a].push_back(b);
    			gr[b].push_back(a);
    		}
    		
    		for(int i=1;i<=n;i++){ 
    			if(!is_visited[i]){ 
    				dfs1(i);
    			}	
    		} 
    		
    		for(int i=n-1;i>=0;i--){ 
    			if(!scc[s[i]]){ 
    				sccnum++;
    				dfs2(s[i]);		
    			} 
    		}
    		//以上是K算法的部分
    		
    		 
    		int cc=0;
    		int u;//u里面是最后一个连通分量的点
    		 
    		//以下检测图有没有连通 
    		for(int i=1;i<=n;i++){ 
    			if(scc[i]==sccnum){ 
    				cc++; 
    				u=i;  
    			}
    		}
    		
    		memset(scc,0,sizeof(scc));
    		dfs2(u);
    		
    		for(int i=1;i<=n;i++){ 
    			if(!scc[i]){ 
    				cc=0;
    				break;
    			}
    		} 
    		
    		cout<<cc<<endl;
    	} 
    	
    }

# Tarjan算法 #

伪代码参考：《算法竞赛入门经典训练指南》

vector<int> G[maxn]
    int pre[maxn]; //最先访问到的节点标号
    int lowlink[maxn];//lowlink[u]为节点u及其后代能追溯到最早(最先被发现)祖先点v的pre(v)值
    int sccno[maxn];//sccno[i]为节点i的连通分量标号
    int dfs_clock; //节点访问标号
    int scc_cnt;   //连通分量标号 
    
    void dfs(int u){ 
    	pre[u]=lowlink[u]=++dfs_clock;
    	S.push(u);
    	
    	for(int i=0;i<G[u].size();i++){ 
    		int v=G[u][i];
    		if(!pre[v]){ 
    			dfs(v);
    			lowlink[u]=min(lowlink[u],lowlink[v]);
    		}else if(!sccno[v]){ 
    			lowlink[u]=min(lowlink[u],pre[v]);
    		}
    	}
    	
    	//找到SCC里面第一个点
    	if(lowlink[u]==pre[u]){ 
    		scc_cnt++; //强连通分量标号+1
    		for(;;){ 
    			int x=S.top();S.pop();
    			sccno[x]=scc_cnt;
    			if(x==u) break; //栈里达到该连通分量的第一个节点的时候
    		}
    	}
    }
    
    void find_scc(int n){ 
    	dfs_clock=scc_cnt=0;
    	memset(sccno,0,sizeof(sccno));
    	memset(pre,0,sizeof(pre));
    	for(int i=0;i<n;i++)
    		if(!pre[i]) dfs(i);
    }

对于poj的popular cows，这个算法需要找出 出度为0的连通分量，然后输出

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<stdlib.h>
    #include<vector>
    #include<stack>
    using namespace std;
    #define LL long long
    #define N 10005
    vector<int> gra[N];
    stack<int>sta;
    int n,m,dfn[N],low[N],vis[N],num[N];
    int degree[N],sum,now,res,loc;
    void init()
    { 
        sum=0;
        now=0;
        res=0;
        memset(vis,0,sizeof(vis));
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(degree,0,sizeof(degree));
        for(int i=0; i<=n; i++)
            gra[i].clear();
        while(!sta.empty())
            sta.pop();
    }
    
    void read()
    { 
        int a,b;
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)
        { 
            scanf("%d%d",&a,&b);
            gra[a].push_back(b);
        }
    }
    
    void tarjan(int s)
    { 
        vis[s]=2;
        dfn[s]=low[s]=++now;
        sta.push(s);
        for(int i=0; i<gra[s].size(); i++)
        { 
            int t=gra[s][i];
            if(dfn[t]==0)
            { 
                tarjan(t);
                low[s]=min(low[s],low[t]);
            }
            else if(vis[t]==2)
                low[s]=min(low[s],dfn[t]);
        }
        if(low[s]==dfn[s])
        { 
            sum++;
            while(!sta.empty())
            { 
                int t=sta.top();
                sta.pop();
                vis[t]=1;
                num[t]=sum;     //缩点
                if(t==s)
                    break;
            }
        }
    }
    
    void solve()
    { 
        for(int i=1; i<=n; i++)
            if(!dfn[i])
                tarjan(i);
        for(int i=1; i<=n; i++)
            for(int j=0; j<gra[i].size(); j++)
                if(num[i]!=num[gra[i][j]])
                    degree[num[i]]++;              //对缩点后的DAG进行出度的统计
        for(int i=1; i<=sum; i++)
        { 
            if(degree[i]==0)
            { 
                res++;
                loc=i;           //第几个强连通分量
            }
        }
        if(res>1)
            printf("0\n");
        else
        { 
            res=0;
            for(int i=1; i<=n; i++)
                if(num[i]==loc)
                    res++;
            printf("%d\n",res);
        }
    }
    
    int main()
    { 
    
        init();
        read();
        solve();
        return 0;

[POJ-2186-Popular Cows]: http://poj.org/problem?id=2186