本文共 1451 字，大约阅读时间需要 4 分钟。

边双连通缩点裸题

因为这是一个连通图,边双连通可以先缩点

这样是一颗树,任意两点间只有一条路

那么统计入度为零的点,用边两两连接起来

每个点的度都大于$2$,这样一定是一个边双

#include 
   
    #include 
    
     #include 
     
      #include 
      
        using namespace std;const int maxn = 2e5+10; struct edge{
   	int u,to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v)	{
    d[++cnt] = (edge){
   u,v,head[u]},head[u] = cnt; }int low[maxn],dfn[maxn],id,bridge[maxn];int bccn,bcc[maxn],n,m,in[maxn];void tarjan(int u,int fa){
   	dfn[u] = low[u] = ++id;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( v==fa )	continue;		if( !dfn[v] )		{
   			tarjan( v,u );			low[u] = min( low[u],low[v] );			if( low[v]>dfn[u] )				bridge[i] = bridge[i^1] = 1;		}		low[u] = min( low[u],dfn[v] );	}}void sd(int u){
   	dfn[u] = 1, bcc[u] = bccn;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( bridge[i]||dfn[v] )	continue;		sd(v);	}}int main(){
   	while( scanf("%d%d",&n,&m)!=EOF )	{
   		for(int i=1;i<=m;i++)		{
   			int l,r; scanf("%d%d",&l,&r);			add(l,r); add(r,l);		}		tarjan(1,1);		memset( dfn,0,sizeof(dfn) );		for(int i=1;i<=n;i++)			if( !dfn[i] )	bccn++,sd(i);		for( int i=2;i<=cnt;i+=2 )		{
   			int u = d[i].u, v = d[i].to;			if( bcc[u]==bcc[v] )	continue;			in[bcc[u]]++, in[bcc[v]]++;		}		int ans = 0;		for(int i=1;i<=bccn;i++)			if( in[i]==1 )	ans++;		printf("%d\n",(ans+1)/2 );		cout << ans << "!\n";		cnt = 1,bccn = id = 0;		for(int i=1;i<=n;i++)			head[i] = dfn[i] = low[i] = bcc[i] = 0;	}}
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109602127 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！