[ Strongly Connected Component - Tarjan & Kosaraju ] 強連通分量的兩種做法(dfs)

一張有向圖，找到所有的 Strongly Connected Component ；亦可進一步收縮所有的 SCC 、收縮所有的環，讓原圖變成 DAG 。

方法1-Tarjan法
跟BCC差不多，直接提供模板:

	#include<vector>
	#include<algorithm>
	#define N 50005
	std::vector<int> s[N];
	int low[N],v[N]={0},Time=0,ans=0,cnt=0;
	int st[N],top=0,contract[N];
	bool instack[N]={0};
	void dfs(int x){
	low[x]=v[x]=++Time;
	st[top++]=x;
	instack[x]=1;
	for(int i=0,r;i<(int)s[x].size();++i){
	if(!v[r=s[x][i]])dfs(r);
	if(instack[r])low[x]=std::min(low[x],low[r]);
	}
	if(v[x]==low[x]){
	int u;
	do{
	instack[u=st[--top]]=0;
	contract[u]=cnt;/*每個點所在的SCC*/
	}while(u!=x);
	++cnt;
	}
	}

view raw SCC_tarjan.cpp hosted with ❤ by GitHub

方法2-Kosaraju
對圖做一次DFS，求他的時間戳，再把圖反向，逆著時間戳進行第二次DFS，所遍歷的點就會是同一個SCC，記得不要走重複的點
以下提供模板:

	#include<vector>
	#include<algorithm>
	#define N 1000005
	std::vector<int >s[N],g[N];/*g是反向圖，要先做好*/
	bool v[N]={0};
	int st[N],top=0,contract[N]={0};
	void dfs(int x){
	v[x]=1;
	for(int i=0;i<(int)s[x].size();++i){
	if(!v[s[x][i]])dfs(s[x][i]);
	}
	st[top++]=x;
	}
	void dfs2(int x,int k){
	if(contract[x])return;
	contract[x]=k;/*x屬於第k個contract*/
	for(int i=0;i<(int)g[x].size();++i){
	dfs2(g[x][i],k);
	}
	}

view raw SCC_DFS.cpp hosted with ❤ by GitHub

用法:

	int n,m;
	int a,b;
	int main(){
	scanf("%d%d",&n,&m);/*n個點m條邊*/
	while(m--){
	scanf("%d%d",&a,&b);
	s[a].push_back(b);
	g[b].push_back(a);/*反向圖*/
	}
	for(int i=0;i<n;++i){
	if(!v[i])dfs(i);/*第一次DFS*/
	}
	for(int i=0;i<top;++i)printf("%d ",st[i]);puts("");
	for(int i=top-1,t=0;i>=0;--i){/*反著處理*/
	if(!contract[st[i]])dfs2(st[i],++t);
	}
	for(int i=0;i<n;i++)printf("%d ",contract[i]);
	return 0;
	}

view raw SCC_DFS_use.cpp hosted with ❤ by GitHub