传送门：

解题思路：

这是一道边双连通图问题。下面是我自己的理解。

双连通图针对的是无向连通图。

双连通图有两类，就是边双连通图，和点双连通图，。其中没有割边的强连通图就是边双连通图 ，没有割点的强连通图就是点双连通图。

双连通图比强连图还要特殊。

而如何把一个非边双连通图，转换成边双连通图呢。先用Tarjan方法，把一个个边双连通分量缩成一个点，然后计算生成的树的叶子节点的个数。

其结果就是（leaf+1)/2;

实现代码:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN=5010;const int MAXM=20010;struct Edge{    int to,next;    bool cut;}edge[MAXM];int head[MAXM],tot;void init(){    memset(head,-1,sizeof(head));    tot=0;}void addEdge(int u,int v){    edge[tot].to=v;    edge[tot].next=head[u];    edge[tot].cut=false;    head[u]=tot++;}int DFN[MAXN],LOW[MAXN],Belong[MAXN],Stack[MAXN];bool Instack[MAXN];int Index,top,brige,block;int Tarjan(int u,int pre){    LOW[u]=DFN[u]=++Index;    Stack[top++]=u;    Instack[u]=true;    int v;    for(int i=head[u];i!=-1;i=edge[i].next){        v=edge[i].to;        if(v==pre) continue;        if(!DFN[v]){            Tarjan(v,u);            if(LOW[u]>LOW[v])                LOW[u]=LOW[v];            if(LOW[v]>DFN[u]){                brige++;                edge[i].cut=true;                edge[i^1].cut=true;            }        }else if(Instack[v]&&LOW[u]>DFN[v]){            LOW[u]=DFN[v];        }    }    if(LOW[u]==DFN[u]){        block++;        do{            v=Stack[--top];            Instack[v]=false;            Belong[v]=block;        }while(v!=u);    }}int deg[MAXN];void solve(int n){    memset(DFN,0,sizeof(DFN));    memset(Instack,0,sizeof(Instack));    Index=top=brige=block=0;    Tarjan(1,0);    memset(deg,0,sizeof(deg));    for(int u=1;u<=n;u++)    for(int i=head[u];i!=-1;i=edge[i].next){        if(edge[i].cut){            deg[Belong[u]]++;        }    }    int ans=0;    for(int i=1;i<=block;i++)        if(deg[i]==1)            ans++;    printf("%d\n",(ans+1)/2);}int main(){    int F,R;    scanf("%d%d",&F,&R);    init();    while(R--){        int u,v;        scanf("%d%d",&u,&v);        addEdge(u,v);        addEdge(v,u);    }    solve(F);    return 0;}