圖論總結（4）有向圖的強連通分量

有向圖的強連通分量：有向圖G中，如果有兩個頂點間至少存在一條路徑，稱兩個頂點強連通（stringly connected），簡稱SCC。

如果有向圖G的每個頂點都強連通，則稱G是一個強連通圖。

非強連通圖的極大強連通子圖，稱為強連通分量。

藍書上給了兩種算法：

一.Kosaraju算法：

按照SCC圖拓撲排序的逆序進行周遊。先正序周遊的到拓撲排序，再構造G的反向圖G2（所有邊相反），最後按拓撲排序的逆序進行周遊。

模闆：

vector<int>G[maxn],G2[maxn];
vector<int>s;
int vis[maxn],sccno[maxn],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);
}
void dfs2(int u){
	if(sccno[u])return ;
	sccno[u]=scc_cnt;
	for(int i=0;i<G2[u].size();i++)dfs2(G[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=1;i<=n;i++)if(!vis[i])dfs1;
	for(int i=n-1;i>=0;i--)if(!sccno[s[i]]){
		scc_cnt++;dfs2[s[i]];
	}
}
           

二.tarjan算法： 定義pre（u）數組為節點u的次序編号（時間戳）。low（u）為u或u的子樹能夠追溯到的最早節點的次序号。 由定義可以得出： low（u）=min（pre(v),low(u)）v為u的子樹且v！=fa； 當DFN（u）=low（u）時，以u為根的搜尋子樹上所有節點是一個強連通分量。 模闆：

vector<int>G[maxn];
int pre[maxn],low[maxn],sccno[maxn];
int dfs_clock,scc_cnt;
stack<int>s;
void dfs(int u){
	pre[u]=low[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);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccno[v]){
			low[u]=min(low[u],pre[v]);
		}
		if(low[u]==pre[u]){
			scc_cnt++;
			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));
	memest(pre,0,sizeof(pre));
	for(int i=0;i<n;i++)
	if(!pre[i])dfs(i);
}
           

個人覺得第一種要好寫一點。 （ 要開學了，感覺圖論總結了就沒時間複習其他了，之後總結就精簡點了。。。）