无向图的边连通分量/桥

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=20010;
int h[N],e[M],nex[M],idx,n,m;
int dfn[N],low[N],timestamp,id[N];
int sk[N],top;
int dcc_cnt,d[N];//每个双联通分量的度
bool is_bridge[N];//记录每条边是否是桥
void add(int x,int y){
    e[idx]=y;
    nex[idx]=h[x];
    h[x]=idx++;
}
void tarjan(int u,int from){
    dfn[u]=low[u]=++timestamp;
    sk[top++]=u;
    for(int i=h[u];~i;i=nex[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]){
                is_bridge[i]=is_bridge[i^1]=1;
            }
        }
        else if(i!=(from^1)){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++dcc_cnt;
        int v;
        do{
            v=sk[--top];
            id[v]=dcc_cnt;
        }while(v!=u);
    }
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    tarjan(1,-1);//如果图联通 跑一次即可
}