Tarjan算法介紹：

Tarjan算法是圖論中的一種算法，用作于圖的聯通性

• 它可以做什麼？

  根據 Robert Tarjan 的名字命名的算法Tarjan算法可以線上性時間内求出無向圖的割點與橋，再進一步的求出雙聯通分量，也在資料結構上做出了貢獻。

  Tarjan算法的用途

  1.求橋和割點

  2.求點和邊的雙連通分量

  3.求強連通*

• 做法基礎

  Tarjan算法基于圖的深度優先周遊上（沒錯！就是與深度優先搜尋（DFS）一樣的東西）

（如果沒學過這樣東西的人可以先收藏一下，等學過了在看）

Targan算法的流程

利用dfs來周遊圖來建構一種數型的結構

Tarjan算法的兩個核心數組

dfn：我們用dfn數組記錄

low：我們用low[i]表示一個節點的子樹中可以到達最小的dfn

（顯然對于一個剛剛周遊到的點我們給他賦上一個新的dfn，low）

‘栗’子來了！

給出一張連通的無向圖G，求出至少加入多少條邊才能使得圖G是一個邊雙連通的。

即求邊雙連通分量把度為一的節點數x （x+1）/2即為答案

注意：求邊雙連通分量時low相同的即為同一組

（标準模闆.cpp）

......
const int M=;
bool map[M][M],vis[M];  
int low[M],dfn[M],cnt[M],num,n,m;
void init(){
    Mt(vis);Mt(map);Mt(low);
    Mt(dfn);Mt(cnt);num=;
}
void dfs(int x,int f){
    dfn[x]=low[x]=++num;
    for(int i=;i<=n;i++){
        if(i!=f&&map[x][i])
            if(!dfn[i]){
                dfs(i,x);
                Min(low[x],low[i]);
            }else Min(low[x],dfn[i]);
    }
}
int main(){
    scanf("%d %d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        map[x][y]=map[y][x]=;
    }dfs(,);
    int ans=;
    for(int i=;i<=n;i++)
        for(int j=;j<=n;j++)
            if(map[i][j])
                if(low[i]!=low[j])//注意：求邊雙連通分量時low相同的即為同一組 
                cnt[low[j]]++;
    for(int i=;i<=n;i++)
        if(cnt[i]==)ans++;
    printf("%d",(ans+)/);
    return ;
}
           

給出一個無向圖，你可以在一些點設定一些出口，使得删去任意一個點之後，其他所有的點都至少與一個出口連通，求在出口數量最小情況下的放置出口的方案。

即求點雙連通分量中割點的數量

我們可以用dfs雙連通分量求。因為每個割點一定是雙連通分量中重複部分

(DFS.cpp)

void tarjan(int x,int f){
    dfn[x]=low[x]=++num;
    for(int i=h[x];i;i=nx[i]){
        int y=g[i];
        if(y==f)continue;
        if(!dfn[y]){
            dfs(y,x);
            Min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                if(!f)deg++;
                else cut[x]=;
            }
        }
    }
}
void dfs(int x){
    vis[x]=T;
    if(cut[x])return;
    Cnt++;
    for(int i=h[i];i;i=nx[i]){
        int y=g[i];
        if(cut[y]&&vis[y]!=T)Cut++,vis[y]=T;
        else if(!vis[y])dfs(y);
    }
}
int main(){
    int n=,m,a,b;
    scanf("%d",&m);
    while(m--){
        scanf("%d %d",&a,&b);
        Max(n,a);
        Max(n,b);
        Add(a,b);
        Add(b,a);
    }
    for(int i=;i<=n;i++){
        if(!dfn[i]){
            deg=;
            tarjan(i,);
            if(deg>)cut[i]=;
        }
    }
    for(int i=;i<=n;i++){
        if(!cut[x]&&!vis[x]){
            Cnt=Cut=;
            T++;
            dfs(i);
            if(Cut==)ans1++,ans2*=Cnt;
            if(!Cut)ans1+=,ans2*=Cnt*(Cnt-);
        }
    }printf("%d %d",ans1,ans2);
}
           

tip：tarjantarjan縮點

void tarjan(int x,int f=){
    dfn[x]=low[x]=++Dfn;
    stk[++top]=x;
    for(int i=;i<G[x].size();i++){
        int y=G[x][i];
        if(y==f)continue;
        if(dfn[y])Min(low[x],dfn[y]);
        else{
            tarjan(y,x);
            Min(low[x],low[y]);
            if(low[y]>dfn[x]){
                /*如果不是和x同一塊就開始縮點*/
                ++tree;
                while(low[stk[top]]>dfn[x])T[stk[top--]]=tree;
            }
        }
    }
}
           

END

https://blog.csdn.net/qq_35392050/article/details/62437074 （30%内容取自處）

Ps：本人的第一篇“半原創”，大佬們勿噴，謝謝！