莫欺少年穷，修魔之旅在这开始—>算法提高课题解

边的双连通分量

思路：

1. tarjan 缩点
2. 遍历所有边，是桥则度数 ++
3. 遍历所有连通分量，度数为 1，则 cnt ++

#include<bits/stdc++.h>

using namespace std;

const int N = 5010, M = 20010;

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool is_bridge[M];
int id[N],dcc_cnt,d[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);

            //是桥，正向边和反向边都置为true
            if(dfn[u]<low[j])
                is_bridge[i]=is_bridge[i^1]=true;
        }

        //非反向边
        else if(i!=(from^1)) low[u]=min(low[u],dfn[j]);
    }

    if(dfn[u]==low[u])
    {
        dcc_cnt++;
        int y;
        do {
            y=stk[top--];
            id[y]=dcc_cnt;
        } while(y!=u);
    }
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    //缩点
    tarjan(1,-1);

    //遍历所有边
    for(int i=0;i<idx;i++)
        if(is_bridge[i])
            d[id[e[i]]]++;

    //遍历所有连通分量，度数为1，则 cnt ++
    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++)
        if(d[i]==1)
            cnt++;

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

    return 0;
}