tarjan算法，一個關於 圖的聯通性的神奇算法。基於DFS算法，深度優先搜索一張有向圖。！注意！是有向圖。根據樹，堆棧，打標記等種種神奇方法來完成剖析一個圖的工作。而圖的聯通性，就是任督二脈通不通。。的問題。
了解tarjan算法之前你需要知道：
強連通，強連通圖，強連通分量，解答樹（解答樹只是一種形式。了解即可）
強連通(strongly connected)： 在一個有向圖G裡，設兩個點 a b 發現，由a有一條路可以走到b，由b又有一條路可以走到a，我們就叫這兩個頂點（a，b）強連通。
強連通圖： 如果 在一個有向圖G中，每兩個點都強連通，我們就叫這個圖，強連通圖。
強連通分量strongly connected
components)：在一個有向圖G中，有一個子圖，這個子圖每2個點都滿足強連通，我們就叫這個子圖叫做 強連通分量 ［分量：：把一個向量分解成幾個方向的向量的和，那些方向上的向量就叫做該向量（未分解前的向量）的分量］
舉個簡單的栗子：
比如說這個圖，在這個圖中呢，點1與點2互相都有路徑到達對方，所以它們強連通.
而在這個有向圖中，點1 2 3組成的這個子圖，是整個有向圖中的強連通分量。
解答樹：就是一個可以來表達出遞歸枚舉的方式的樹（圖），其實也可以說是遞歸圖。。反正都是一個作用，一個展示從“什麼都沒有做”開始到“所有結求出來”逐步完成的過程。“過程！”
tarjan算法，之所以用DFS就是因為它將每一個強連通分量作為搜索樹上的一個子樹。而這個圖，就是一個完整的搜索樹。
為了使這顆搜索樹在遇到強連通分量的節點的時候能順利進行。每個點都有兩個參數。
1， DFN［］作為這個點搜索的次序編號（時間戳），簡單來說就是 第幾個被搜索到的。％每個點的時間戳都不一樣％。
2， LOW［］作為每個點在這顆樹中的，最小的子樹的根，每次保證最小，喜歡它的父親結點的時間戳這種感覺。如果它自己的LOW［］最小，那這個點就應該從新分配，變成這個強連通分量子樹的根節點。
ps：每次找到一個新點，這個點LOW［］＝DFN［］。
而為了存儲整個強連通分量，這裡挑選的容器是，堆棧。每次一個新節點出現，就進站，如果這個點有 出度 就繼續往下找。直到找到底，每次返回上來都看一看子節點與這個節點的LOW值，誰小就取誰，保證最小的子樹根。如果找到DFN［］＝＝LOW［］就說明這個節點是這個強連通分量的根節點（畢竟這個LOW［］值是這個強連通分量裡最小的。）最後找到強連通分量的節點後，就將這個棧裡，比此節點後進來的節點全部出棧，它們就組成一個全新的強連通分量。
先來一段偽代碼：
tarjan(u){
DFN[u]=Low[u]=++Index // 為節點u設定次序編號和Low初值
Stack.push(u) // 將節點u壓入棧中
for each (u, v) in E // 枚舉每一條邊
if (v is not visted) // 如果節點v未被訪問過
tarjan(v) // 繼續向下找
Low[u] = min(Low[u], Low[v])
else if (v in S) // 如果節點u還在棧內
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u]) // 如果節點u是強連通分量的根
repeat v = S.pop // 將v退棧，為該強連通分量中一個頂點
print v
until (u== v)
}
首先來一張有向圖。網上到處都是這個圖。我們就一點一點來模擬整個算法。
從1進入 DFN［1］＝LOW［1］＝ ＋＋index －－－－1
入棧 1
由1進入2 DFN［2］＝LOW［2］＝ ＋＋index －－－－2
入棧 1 2
之後由2進入3 DFN［3］＝LOW［3］＝ ＋＋index －－－－3
入棧 1 2 3
之後由3進入 6 DFN［6］＝LOW［6］＝＋＋index －－－－4
入棧 1 2 3 6
之後發現6無出度，之後判斷 DFN［6］＝＝LOW［6］
說明6是個強連通分量的根節點：6及6以後的點 出棧。
棧： 1 2 3
之後退回 節點3 Low[3] = min(Low[3], Low[6]) LOW［3］還是 3
節點3 也沒有再能延伸的邊了，判斷 DFN［3］＝＝LOW［3］
說明3是個強連通分量的根節點：3及3以後的點 出棧。
棧： 1 2
之後退回 節點2 嗯？！往下到節點5
DFN［5］＝LOW［5］＝ ＋＋index －－－－－5
入棧 1 2 5
ps：你會發現在有向圖旁邊的那個丑的（劃掉）搜索樹 用紅線剪掉的子樹，那個就是強連通分量子樹。每次找到一個。直接。一剪子下去。半個子樹就沒有了。。
結點5 往下找，發現節點6 DFN［6］有值，被訪問過。就不管它。
繼續 5往下找，找到了節點1 他爸爸的爸爸。。DFN［1］被訪問過並且還在棧中，說明1還在這個強連通分量中，值得發現。 Low[5] = min(Low[5], DFN[1])
確定關系，在這棵強連通分量樹中，5節點要比1節點出現的晚。所以5是1的子節點。So
LOW［5］＝ 1
由5繼續回到2 Low[2] = min(Low[2], Low[5])
LOW［2］＝1；
由2繼續回到1 判斷 Low[1] = min(Low[1], Low[2])
LOW［1］還是 1
1還有邊沒有走過。發現節點4，訪問節點4
DFN［4］＝LOW［4］＝＋＋index －－－－6
入棧 1 2 5 4
由節點4，走到5，發現5被訪問過了，5還在棧裡，
Low[4] = min(Low[4], DFN[5]) LOW［4］＝5
說明4是5的一個子節點。
由4回到1.
回到1，判斷 Low[1] = min(Low[1], Low[4])
LOW［1］還是 1 。
判斷 LOW［1］ ＝＝ DFN［1］
诶？！相等了 說明以1為根節點的強連通分量已經找完了。
將棧中1以及1之後進棧的所有點，都出棧。
棧 ：（鬼都沒有了）
這個時候就完了嗎？！
你以為就完了嗎？！
然而並沒有完，萬一你只走了一遍tarjan整個圖沒有找完怎麼辦呢？！
所以。tarjan的調用最好在循環裡解決。
like 如果這個點沒有被訪問過，那麼就從這個點開始tarjan一遍。
因為這樣好讓每個點都被訪問到。
基本思路：
1.初始化
2.入棧
3.枚舉：
1.不在隊列中->訪問，進行賦值，
2.在隊列中->賦值
4.尋找根->輸出結果
來一道裸代碼。
輸入：
一個圖有向圖。
輸出：
它每個強連通分量。
這個圖就是剛才講的那個圖。一模一樣。
input:
6 8
1 3
1 2
2 4
3 4
3 5
4 6
4 1
5 6
output:
6
5
3 4 2 1
a Sans Unicode";
mso-hansi-font-family:"Lucida Sans Unicode";mso-bidi-font-family:"Lucida Sans Unicode";
color:black'>的一個子節點。
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
struct node {
int v,next;
} edge[1001];
int DFN[1001],LOW[1001];
int stack[1001],heads[1001],visit[1001],cnt,tot,index;
void add(int x,int y) {
edge[++cnt].next=heads[x];
edge[cnt].v = y;
heads[x]=cnt;
return ;
}
void tarjan(int x) { //代表第幾個點在處理。遞歸的是點。
DFN[x]=LOW[x]=++tot;// 新進點的初始化。
stack[++index]=x;//進站
visit[x]=1;//表示在棧裡
for(int i=heads[x]; i!=-1; i=edge[i].next) {
if(!DFN[edge[i].v]) {
//如果沒訪問過
tarjan(edge[i].v);//往下進行延伸，開始遞歸
LOW[x]=min(LOW[x],LOW[edge[i].v]);//遞歸出來，比較誰是誰的兒子／父親，就是樹的對應關系，涉及到強連通分量子樹最小根的事情。
} else if(visit[edge[i].v ]) {
//如果訪問過，並且還在棧裡。
LOW[x]=min(LOW[x],DFN[edge[i].v]);//比較誰是誰的兒子／父親。就是鏈接對應關系
}
}
if(LOW[x]==DFN[x]) { //發現是整個強連通分量子樹裡的最小根。
do {
printf("%d ",stack[index]);
visit[stack[index]]=0;
index--;
} while(x!=stack[index+1]);//出棧，並且輸出。
printf("\n");
}
return ;
}
int main() {
memset(heads,-1,sizeof(heads));
int n,m;
scanf("%d%d",&n,&m);
int x,y;
for(int i=1; i<=m; i++) {
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1; i<=n; i++)
if(!DFN[i]) tarjan(1);//當這個點沒有訪問過，就從此點開始。防止圖沒走完
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
struct node
{
int u;
int v;
int w;
int next;
}edge[101];
int head[101];
int num=1;
void add(int x,int y)
{
edge[num].u=x;
edge[num].v=y;
edge[num].next=head[x];
head[x]=num++;
}
int dfn[1001];// 既可以用來表示一個點的被訪問的順序，又可以判斷是否出現過
int low[1001];
int stack[101];
int top=0;
int now=0;// 已經訪問的數的數量
int vis[1001];//表示是否在棧中
void tarjan(int x)
{
vis[x]=1;
dfn[x]=low[x]=++now;
stack[++top]=x;
for(int i=head[x];i!=-1;i=edge[i].next)
{
if(!dfn[edge[i].v])
{
tarjan(edge[i].v);
low[x]=min(low[x],low[edge[i].v]);
}
else if(vis[edge[i].v])
{
low[x]=min(low[x],dfn[edge[i].v]);
}
}
if(low[x]==dfn[x])
{
do
{
printf("%d ",stack[top]);
vis[stack[top]]=0;
top--;
}while(x!=stack[top+1]);
putchar('\n');
}
return;
}
int main()
{
for(int i=1;i<=101;i++)
head[i]=-1;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
{
tarjan(i);
}
}
return 0;
}
