算法思路：
??

????? ?這個算法思路不難理解，任何一個強連通分量，必定是對原圖的深度優(yōu)先搜索樹的子樹。

?????? 那么其實，我們只要確定每個強連通分量的子樹的根，然后根據(jù)這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那么眼下的問題就只

剩下如何確定強連通分量的根和如何從最低層開始拿出強連通分量了。
?????

?????? 那么如何確定強連通分量的根，在這里我們維護兩個數(shù)組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與

頂點i鄰接的頂點，未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發(fā)現(xiàn)mlik[i]==indx[i]那么，

當前頂點就是一個強連通分量的根，為什么呢？因為如果它不是強連通分量的跟，那么它一定是屬于另一個強連通分量，而且它的根是當前頂點的祖

宗，那么存在包含當前頂點的到其祖宗的回路，可知mlik[i]一定被更改為一個比indx[i]更小的值。

????? 至于如何拿出強連通分量，這個其實很簡單，如果當前節(jié)點為一個強連通分量的根，那么它的強連通分量一定是以該根為根節(jié)點的(剩下節(jié)點)子

樹。在深度優(yōu)先遍歷的時候維護一個堆棧，每次訪問一個新節(jié)點，就壓入堆棧。現(xiàn)在知道如何拿出了強連通分量了吧？是的，因為這個強連通分量時最

先被壓人堆棧的，那么當前節(jié)點以后壓入堆棧的并且仍在堆棧中的節(jié)點都屬于這個強連通分量。當然有人會問真的嗎？假設(shè)在當前節(jié)點壓入堆棧以后壓

入并且還存在，同時它不屬于該強連通分量，那么它一定屬于另一個強連通分量，但當前節(jié)點是它的根的祖宗，那么這個強連通分量應(yīng)該在此之前已經(jīng)

被拿出。現(xiàn)在沒有疑問了吧，那么算法介紹就完了。

?

題目：Triangle LOVE

?

題意：給定一個有向圖并規(guī)定：每兩個點之間一定有邊，同時A指向B則B定不能指向A，反之亦然。 詢問是否存在僅有三個點構(gòu)成的環(huán)。

?

思路：

首先判斷有向圖中是否存在環(huán)馬上有tarjan能夠很好的解決。并且如果存在大于三個點以上的環(huán)的話肯定存在僅有三個點構(gòu)成的環(huán)。 因為每兩

個點之間都有邊，并且只有一個給定的指向，畫幾個圖便可以推導出這樣的結(jié)論。

證明：?假設(shè)存在一個n元環(huán)，因為a->b有邊，b->a必定沒邊，反之也成立 所以假設(shè)有環(huán)上三個相鄰的點a-> b-> c,那么如果c->a間有邊，就已經(jīng)形

成了一個三元環(huán)，如果c->a沒邊，那么a->c肯定有邊，這樣就形成了一個n-1元環(huán)。。。。 所以只需證明n為4時一定有三元環(huán)即可，顯然成立。 所

以知道在tarjan后或中判斷是否存在大于等于三個點的強連通圖。復雜度為邊數(shù)即O(n*n)。

?

#include <iostream> #include <string.h> #include <stdio.h>using namespace std;const int N=2005;int head[N],low[N]; int dfn[N],stack[N]; int ans[N]; bool temp[N]; char str[N][N]; int index,m,flag;typedef struct {int to;int next; }Node;Node map[N*N];void add(int u,int v) {map[index].to=v;map[index].next=head[u];head[u]=index++; }void Tarbfs(int k,int lay,int &scc_num) {int t;temp[k]=1;low[k]=lay;dfn[k]=lay;stack[m++]=k;for(int i=head[k];i!=-1;i=map[i].next){t=map[i].to;if(!dfn[t]){Tarbfs(t,++lay,scc_num);if(flag) return;low[k]=min(low[k],low[t]);}if(temp[t]){low[k]=min(low[k],dfn[t]);}}if(dfn[k]==low[k]){++scc_num;while(1){t=stack[--m];temp[t]=0;ans[scc_num]++;if(ans[scc_num]>=3){flag=1;return;}if(t==k) break;}}if(flag) return; }int Tarjan(int n) {int scc_num=0,lay=1;m=0;memset(temp,0,sizeof(temp));memset(low,0,sizeof(low));for(int i=1;i<=n;i++){if(!dfn[i])Tarbfs(i,lay,scc_num);if(flag) break;}return scc_num; }int main() {int i,j,n,t=1,T;scanf("%d",&T);while(T--){scanf("%d",&n);memset(dfn,0,sizeof(dfn));memset(ans,0,sizeof(ans));memset(head,-1,sizeof(head));memset(stack,0,sizeof(stack));index=flag=0;for(i=1;i<=n;i++)scanf("%s",str[i]+1);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(str[i][j]=='1'){add(i,j);}}}printf("Case #%d: ",t++);Tarjan(n);if(flag) puts("Yes");else puts("No");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU4324(强连通的Tarjan算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。