tarjan判边-双连通分量(eBCC)

#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

const int N=5005;
const int M=20005;
int n, m;
int head[N], E=0;
int dfn[N], low[N], ts=0;
stack<int> st;
int id[N], ebcc_cnt=0; // 边双连通分量计数
bool is_bridge[N];
int d[N]; // 统计点的度数

struct Edge{int v, ne;}e[M];

inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

void tarjan(int u, int from){
    dfn[u]=low[u]=++ts;
    st.push(u);
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){ // 如果是树枝边
            tarjan(v, i);
            low[u]=min(low[u], low[v]);
            if(dfn[u]<low[v]){ // 连续的较小的偶数和较大的奇数构成桥, (0, 1), (2,3), (4,5)
                is_bridge[i]=is_bridge[i^1]=true; 
            }
        }
        else if(i!=(from^1)){ // 如果不是反向边更新low[u]
            low[u]=min(low[u], dfn[v]);
        }
    }

    if(dfn[u]==low[u]){ 
        ++ebcc_cnt;
        int j;
        do{
            j=st.top(); st.pop(); id[j]=ebcc_cnt;
        }while(j!=u);
    }
}

int main(){
    cin>>n>>m;
    memset(head, -1, sizeof head);
    while(m--){
        int a, b;
        // 建立无向图
        cin>>a>>b;
        add(a, b);
        add(b, a);
    }

    tarjan(1, -1);
    for(int i=0; i<E; ++i){
        if(is_bridge[i]) d[id[e[i].v]]++;
    }


    // 统计缩点后度数为1的点
    // 根据结论计算, 需要添加边的数量为(cnt+1)/2
    int cnt=0;
    for(int i=1; i<=ebcc_cnt; ++i)
        if(d[i]==1) ++cnt;

    cout<<(cnt+1)/2<<endl;

    return 0;
}