Tarjan學習筆記

最後的DFS樹是這樣的

按照我們找到的根節點拆成一個個的強連通分量

這樣就完成了

我們把以一號為開始的連通圖都遍歷一遍了...為了防止圖有多個(不連通) 我們要在調用Tarjan的時候這樣寫

for(int i = 1; i <= n; ++i) 
  if(!dfn[i]) Tarjan(i); //如果沒有時間戳,那就代表沒有遍歷到,從此點開始Tarjan

這樣就可以把所有的圖都給遍歷一遍了...

來一道裸代碼。
輸入：
一個圖有向圖。
輸出：
它每個強連通分量。

這個圖就是剛纔講的那個圖。一模一樣。

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


代碼:

#include <cstdio>
#include <algorithm>

using namespace std;

struct node {
    int to,next;
} edge[1001];

int cnt,Index,top;
int dfn[1001],low[1001];
int stack[1001],head[1001],visit[1001];

void add(int x,int y) {
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    head[x] = cnt;
}
void tarjan(int x) { //代表第幾個點在處理。遞歸的是點。
    dfn[x] = low[x] = ++Index; // 新進點的初始化。
    stack[++top] = x; //進棧 
    visit[x] = 1; //表示在棧里
    for(int i = head[x]; i; i = edge[i].next) {
        if(!dfn[edge[i].to]) { //如果沒訪問過
            tarjan(edge[i].to); //往下進行延伸，開始遞歸
            low[x] = min(low[x],low[edge[i].to]);//遞歸出來，比較誰是誰的兒子／父親，就是樹的對應關係，涉及到強連通分量子樹最小根的事情。
        } else if(visit[edge[i].to]) { //如果訪問過，並且還在棧里。
            low[x] = min(low[x],dfn[edge[i].to]);//比較誰是誰的兒子／父親。就是鏈接對應關係
        }
    }
    if(low[x] == dfn[x]) { //發現是整個強連通分量子樹里的最小根。
        do {
            printf("%d ",stack[top]);
            visit[stack[top]] = 0;
            top--;
        } while(x != stack[top+1]);//出棧，並且輸出。
        printf("\n");
    }
    return ;
}
int main() {
    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(i);//當這個點沒有訪問過，就從此點開始。防止圖沒走完
    return 0;
}