求边双联通分量, 然后组成一颗树, 叶子结点两两配对即可
By: 大奕哥
- #include<bits/stdc++.h>
- using namespace std;
- const int N=100005;
- 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;
- struct node{
- int f,to,nex;
- }e[200050];
- void add(int x,int y)
- {
- e[++cnt].to=y;e[cnt].f=x;e[cnt].nex=head[x];head[x]=cnt;
- }
- void tarjan(int x,int f)
- {
- dfn[x]=low[x]=++idx;s[++top]=x;in[x]=1;
- for(int i=head[x];i;i=e[i].nex)
- {
- int y=e[i].to;
- if(fa[i]==f)continue;
- if(!dfn[y])
- {
- tarjan(y,fa[i]);
- low[x]=min(low[x],low[y]);
- }
- else if(in[y])
- low[x]=min(dfn[y],low[x]);//in 数组无向图不必加, 有向图必加
- }
- if(low[x]==dfn[x])
- {
- num++;int a=-1;
- do{
- a=s[top--];
- in[a]=0;
- col[a]=num;
- }while(a!=x);
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;++i)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- add(x,y);fa[cnt]=++p;
- add(y,x);fa[cnt]=p;
- }
- for(int i=1;i<=n;++i)
- if(!dfn[i]){
- tarjan(i,0);
- }
- for(int i=1;i<=cnt;++i)
- {
- int x=e[i].f;int y=e[i].to;
- if(col[x]==col[y])continue;
- du[col[x]]++;du[col[y]]++;
- }
- for(int i=1;i<=num;++i)
- if(du[i]==2)ans++;
- printf("%d\n",ans+1>>1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2495743.html