求強聯通分量有很多種。 《C++信息學奧賽一本通》 ?中講過一個dfs求強聯通分量的算法Kosdaraju，為了騙字數我就待會簡單的說說。然而我們這篇文章的主體是Tarjan，所以我肯定說完之后再贊揚一下Tarjan大法好是不是

　　首先我們講一下強聯通分量

　　強聯通分量指的是圖的一個子圖。在這個子圖中，任意兩個節點都可以互相到達。從定義上我們就可以看出是一個有向圖來，因為任意一個無向圖都符合該定義。

　　而它的標準定義是：有向圖中任意兩點都聯通的最大子圖。

?　　　　　　　　　　　　　　　　　　　　

　　咳咳，首先慶祝一下哈——本人博客的第一張圖。繪圖歷時3分鐘。

　　在咱們舉的例子中，可以看出1 、2 、3 、5 通過邊可以相互到達，它們算一個強聯通分量，但4卻被它們隔絕在外。從圖中可以看出，從4點出發不能到達任意一個點。所以它單個節點也算一個強聯通分量。所以圖中的強聯通分量有兩個：一個是1-2-3-5，一個是4。

　　ok看完了強聯通分量是什么我們就講一下Kosaraju。

　　這個算法的思路是，對圖進行DFS并記錄每個點的退出順序。再構造反圖(就是有向邊的方向全都反過來),按照退出順序的逆序DFS反圖，對得到的點進行染色即為強聯通分量。

　　講完思路開始模擬。以起點1為起點遍歷順序如下：

　　[ 1 2 3 5 4 ?5?3 2?4 4?1 ]

　　加粗斜體外帶下劃線的部分就是本圖的退出順序。

　　于是我們得到這樣一個數組：[ 5 3 2 4 1 ] 。按照這個數組的逆序對反圖遍歷得到：

　　[ 5 3 2 1 退出 4 退出 ]

　　即得到要求的兩個強聯通分量。

　　還要兩遍DFS，麻煩的一比。看我大Tarjan一遍DFS就能求出強聯通分量

　　首先我們要明確Tarjan要用到的兩個數組：dfn[] 和 low[]?

　　dfn指的是在DFS過程中訪問到該點的順序。從1開始DFS全圖，那么1的dfn值就是1，2的dfn值是2,5的dfn值是4，4的dfn值是5。剩下的一個類推

　　那么low呢？low指的是如果逆著DFS序往前回溯，該節點最早是由哪個節點走過來的。

　　比如在上圖中2 、3 、5 、4 最早都是由1走過來的，所以它們的low值都是1

　　下面貼出dfn和low的算法

每次dfs(點u){

　　dfn[u] = 進入 dfs() 函數的次數 ?（自己定義一個時間戳記錄 如 time）

? ? ? ?枚舉與其相鄰的點v{

? ?　　 ? ? 如果 沒有 訪問過點v { ? ( 就是dfs樹上的樹邊 )

　　　　　　　　dfs(v);

　　　　　　　　如果 v 能追溯 到 比“u 追溯到的最早的點” 更早的點；

　　　　　　　　那么 u 就能 通過 v 來追溯到 那個點；

　　　　　　　　low[u]=min(low[u],low[v]);

　　　　 ?}

?　　　　 ?如果 訪問過點v && v在棧中

　　　　　　　low[u]=min(low[u],dfn[v]);?

? ? ?}

　　縮點

}

　　上面那些偽代碼是從偉大的GeneralLiu那里帶過來的，在此先%%%

　　然后 ?假設我們走到一個節點i，發現這個i不能繼續擴展了，也就是dfn[i]==low[i]

　　于是我們開始往回走。往回走的過程中，我們就把和它一個分量的節點進行染色，給它們統一的標記。　　最后統計有多少種不同的標記即是強聯通分量個數

　　luogu的一道題刻錄光盤非常好，可以用于練手。

　　放代碼

#include<iostream> #include<cstring> using namespace std; int head[10000],num; struct Edge{int next,to; }edge[100000]; int stack[10000],top; int color[10000],cnt; int dfn[10000],low[10000]; int ID; bool jd[10000]; int vis[10000]; inline void add(int from,int to){edge[++num]={head[from],to};head[from]=num; }void tarjan(int x){dfn[x]=++ID;low[x]=ID;jd[x]=1;stack[++top]=x;for(int i=head[x];i;i=edge[i].next){int to=edge[i].to;if(!dfn[to]){tarjan(to);low[x]=min(low[x],low[to]);}else if(jd[to]) low[x]=min(low[x],dfn[to]);}if(dfn[x]==low[x]){jd[x]=0;color[x]=++cnt;while(stack[top]!=x){color[stack[top--]]=cnt;jd[stack[top+1]]=0;color[stack[top+1]]=cnt;}top--;}}int main(){int n;cin>>n;int x;for(int i=1;i<=n;++i){while(cin>>x&&x!=0){add(i,x);}}for(int i=1;i<=n;++i){if(!dfn[i]) tarjan(i);}memset(jd,0,sizeof(jd));for(int i=1;i<=n;++i){for(int j=head[i];j;j=edge[j].next){if(color[i]!=color[edge[j].to]){jd[color[edge[j].to]]=1;}}}int ans=0;for(int i=1;i<=cnt;++i) if(!jd[i]) ans++;cout<<ans<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/cellular-automaton/p/6895397.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Tarjan的强联通分量的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。