求边双联通分量，然后组成一颗树，叶子结点两两配对即可。
By：大奕哥
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100005; 4 int head[N],low[N],fa[200050],p,dfn[N],in[N],s[N],top,idx,cnt,num,col[N],du[N],ans,n,m; 5 struct node{ 6 int f,to,nex; 7 }e[200050]; 8 void add(int x,int y) 9 { 10 e[++cnt].to=y;e[cnt].f=x;e[cnt].nex=head[x];head[x]=cnt; 11 } 12 void tarjan(int x,int f) 13 { 14 dfn[x]=low[x]=++idx;s[++top]=x;in[x]=1; 15 for(int i=head[x];i;i=e[i].nex) 16 { 17 int y=e[i].to; 18 if(fa[i]==f)continue; 19 if(!dfn[y]) 20 { 21 tarjan(y,fa[i]); 22 low[x]=min(low[x],low[y]); 23 } 24 else if(in[y]) 25 low[x]=min(dfn[y],low[x]);//in数组无向图不必加，有向图必加。 26 } 27 if(low[x]==dfn[x]) 28 { 29 num++;int a=-1; 30 do{ 31 a=s[top--]; 32 in[a]=0; 33 col[a]=num; 34 }while(a!=x); 35 } 36 } 37 int main() 38 { 39 scanf("%d%d",&n,&m); 40 for(int i=1;i<=m;++i) 41 { 42 int x,y; 43 scanf("%d%d",&x,&y); 44 add(x,y);fa[cnt]=++p; 45 add(y,x);fa[cnt]=p; 46 } 47 for(int i=1;i<=n;++i) 48 if(!dfn[i]){ 49 tarjan(i,0); 50 } 51 for(int i=1;i<=cnt;++i) 52 { 53 int x=e[i].f;int y=e[i].to; 54 if(col[x]==col[y])continue; 55 du[col[x]]++;du[col[y]]++; 56 } 57 for(int i=1;i<=num;++i) 58 if(du[i]==2)ans++; 59 printf("%d ",ans+1>>1); 60 return 0; 61 }