無向圖的割點與橋

定義

對于無向連通圖G=(V,E)，Tarjan算法可以線上性時間内求出無向圖的割點和橋。

割點：對于x∈V，如果删除某個點x，圖的聯通分量增多（G分裂為兩個或者兩個以上的子圖），則x為割點。

橋    ：對于e∈E，如果删除e，G分裂成兩個不相連的子圖，則稱e為橋或割邊。

時間戳（T[i]）：DFS的過程中，第一次通路到節點的時間，将N個節點依次标記為1-N。

搜尋樹：按照DFS的順序建樹。

追溯值（low[i]）：low[i] = min(T[i通過不在搜尋樹上的邊到達的點] , i的子樹中的節點)。

割邊判定法則：當節點x的子節點y滿足T[x] < low[y] 時，邊（x，y）為橋。  證明：當T[x] < T[y] 時 y走除了（x，y）外的任意邊都無法到達時間戳更小的節點。

橋一定是搜尋樹中的邊，簡單環中的邊一定都不是橋。

模闆（完美支援重邊 powered by 李煜東）

#include <bits/stdc++.h>
using namespace std;


const int maxn = 1e5+10;
int dfn[maxn],low[maxn],n,num,tot,m;
int head[maxn],ver[maxn<<1],Next[maxn<<1];
bool bridge[maxn<<1];


void add(int x , int y)
{
    ver[++tot] = y,Next[tot]=head[x],head[x] = tot;
}
void Tarjan(int x, int in_edge)
{
    dfn[x] = low[x] =  ++num;
    for(int i = head[x] ; i ; i = Next[i])
    {
        int y = ver[i];
        if(!dfn[y])
        {
            Tarjan(y,i);
            low[x] = min(low[x],low[y]);

            if(low[y] > dfn[x])
            {
                bridge[i] = bridge[i^1] = true;
            }
        }
        else if(i != (in_edge^1))
        {
            low[x] = min(low[x] , dfn[y]);
        }
    }
}

int main()
{
    cin >> n >> m;
//    num = 0;
    tot = 1;
    for(int i = 0 ; i < m ; i++)
    {
        int x,y;
        cin >> x >> y;
        add(x,y);add(y,x);
    }

    for(int i = 1 ; i <= n ; i++)
    {
        if(!dfn[i])
            Tarjan(i,0);
    }

    for(int i = 2 ; i < tot ; i += 2 )
    {
        if(bridge[i])printf("%d %d\n",ver[i^1],ver[i]);
    }
}