Tarjan求割边、桥

Author： YorkWu
发布时间：March 12, 2019
1163 views
No comments
1069 words
Categories：类目 OI

Tarjan求割点、桥

#### 割边判定法则

*   无向边$(x,y)$是桥，当且仅当搜索树上x的子节点y，满足$dfn\[x\] < low\[y\]$。
*   **桥一定是搜索树上的边**，并且**一个简单环中的边一定不是桥！**

求出一个无向图中所有的桥：

#include<bits/stdc++.h>
    using namespace std;
    const int SIZE=100009;
    struct Edge{
        int to,next;
    }e[SIZE*2];
    int head[SIZE],dfn[SIZE],low[SIZE],n,m,tot,num;
    bool bridge[SIZE*2];
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    
    void tarjan(int x,int in_edge){
        dfn[x]=low[x]=++num;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(!dfn[y]){
                tarjan(y,i);
                low[x]=min(low[x],low[y]);
                if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=1;
            }
            else if(i!=(in_edge^1)){
                low[x]=min(low[x],dfn[y]);
            }
        }
    }
    
    int main(){
        cin>>n>>m;
        tot=1;//一定要从2开始存边！！！
        for(int i=1;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]) cout<<e[i].to<<" "<<e[i^1].to<<endl;
        }
        return 0;
    }

Last modification：March 14, 2020