// eDCC缩点 Tarjan算法 O(n+m)
#include<bits/stdc++.h>
using namespace std;

const int N=5010,M=20010;
int to[M],ne[M],h[N],idx=1; //2,3异或配对
void add(int a,int b){
  to[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
int n,m,sum;
int dfn[N],low[N],stk[N],top,dcc[N],cnt;
int bri[M],deg[N];

void tarjan(int x,int e){
  dfn[x]=low[x]=++dfn[0]; stk[++top]=x;
  for(int i=h[x];i;i=ne[i]){
    int y=to[i];
    if(!dfn[y]){ //若y未访问
      tarjan(y,i);
      low[x]=min(low[x],low[y]);
      
      if(low[y]>dfn[x]) bri[i]=bri[i^1]=1; //标记割边
    }
    else if(i!=(e^1)) //若y已访问且不是反边
      low[x]=min(low[x],dfn[y]);
  }
  
  if(low[x]==dfn[x]){ //若x是edcc的根
    ++cnt;
    while(stk[top+1]!=x) dcc[stk[top--]]=cnt;
  }
}
int main(){
  cin>>n>>m;
  for(int a,b;m--;)cin>>a>>b,add(a,b),add(b,a);

  tarjan(1,0);
  
  for(int i=2;i<=idx;i++) //枚举原始边
    if(bri[i]) deg[dcc[to[i]]]++; //如果是割边，统计割边端点的度

  for(int i=1;i<=cnt;i++) //枚举缩点（树节点）
    if(deg[i]==1) sum++; //统计叶节点个数
  cout<<(sum+1>>1);
}

题解1：基于双连通分量的桥计数问题

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=1e4+10;
struct node{int x,y;}E[M];
vector<pair<int,int>>G[N];bool brg[M];
int n,m,cnt,tsp,low[N],dfn[N],edcc[N],d[N];
stack<int>stk;bool instk[N];
void tarjan(int x,int in_id)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);instk[x]=1;
    for(auto i:G[x])if(i.second!=in_id)
    {
        int y=i.first,id=i.second;
        if(dfn[y]==0)
        {
            tarjan(y,id);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])brg[id]=1;
        }
        else if(instk[y]==1)low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=0;z!=x;)
        {
            z=stk.top();stk.pop();instk[z]=0;
            edcc[z]=cnt;
        }
    }
}
 
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        E[i]={x,y};
        G[x].push_back({y,i});
        G[y].push_back({x,i});
    }
    tsp=cnt=0;memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);
    memset(brg,0,sizeof brg);memset(edcc,0,sizeof(edcc));
    tarjan(1,0);
     
    memset(d,0,sizeof d);
    for(int i=1;i<=m;i++)if(brg[i])d[edcc[E[i].x]]++,d[edcc[E[i].y]]++;
    int sum=0;
    for(int i=1;i<=cnt;i++) if(d[i]==1) sum++;
    printf("%d\n",(sum+1)>>1); 
    return 0;
}

题解2：基于邻接表的桥计数问题

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=2e4+10;
struct edge{int x,y,pre;}a[M];bool bridge[M];int alen,last[N];
void add(int x,int y){ alen++;a[alen]={x,y,last[x]};last[x]=alen;}
int n,m,cnt,tsp,low[N],dfn[N],edcc[N],d[N];
stack<int>sta;
void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++tsp;
    sta.push(x);
    for(int k=last[x];k;k=a[k].pre)if(k!=(in_edge^1))
    {
        int y=a[k].y;
        if(dfn[y]==0)
        {
            tarjan(y,k);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])bridge[k]=bridge[k^1]=1;
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=0;z!=x;)
        {
            z=sta.top();sta.pop();
            edcc[z]=cnt;
        }
    }
}
 
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    alen=1;memset(last,0,sizeof last);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    tsp=cnt=0;memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);
    memset(bridge,0,sizeof bridge);memset(edcc,0,sizeof(edcc));
    tarjan(1,0);
     
    memset(d,0,sizeof d);
    for(int k=2;k<=alen;k+=2)if(bridge[k])d[edcc[a[k].x]]++,d[edcc[a[k].y]]++;
    int sum=0;
    for(int i=1;i<=cnt;i++) if(d[i]==1) sum++;
    printf("%d\n",(sum+1)>>1); 
    return 0;
}