【题意】给定无向连通图，要求添加最少的边使全图变成边双连通分量。

【算法】Tarjan缩点

【题解】首先边双缩点，得到一棵树（无向无环图）。 

入度为1的点就是叶子，两个LCA为根的叶子间合并最高效，直接将两个叶子并入双连通分量后建新图。

若没有两个LCA为根的叶子则往下换根。

ans=(num+1)/2。

猜想：如果要统计方案的话，就每次并后再次缩点，找一个非叶子作为根。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=5010,maxm=20010;struct edge{
    int u,v,from;}e[maxm];int first[maxn],n,m,tot=1,col[maxn],dfn[maxn],low[maxn],cnt,in[maxn],ans;bool iscut[maxm];void insert(int u,int v){tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void tarjan(int x,int fa){    dfn[x]=low[x]=++cnt;    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){        if(!dfn[e[i].v]){            tarjan(e[i].v,x);            low[x]=min(low[x],low[e[i].v]);            if(low[e[i].v]>dfn[x])iscut[i]=iscut[i^1]=1;        }        else low[x]=min(low[x],dfn[e[i].v]);    }}void dfs(int x,int k){    col[x]=k;    for(int i=first[x];i;i=e[i].from)if(!iscut[i]&&!col[e[i].v]){        dfs(e[i].v,k);    }}int main(){    scanf("%d%d",&n,&m);    int u,v;    for(int i=1;i<=m;i++){        scanf("%d%d",&u,&v);        insert(u,v);insert(v,u);    }    tarjan(1,0);    cnt=0;    for(int i=1;i<=n;i++)if(!col[i])dfs(i,++cnt);    for(int i=1;i<=tot;i+=2)if(col[e[i].u]!=col[e[i].v])in[col[e[i].u]]++,in[col[e[i].v]]++;    ans=0;    for(int i=1;i<=cnt;i++)if(in[i]==1)ans++;    printf("%d",(ans+1)/2);    return 0;}