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

$简短代码模板$

主要思想就是找割点

发现$low[v]>=dfn[u]$说明无法通过非返祖边回到原来的集合,这就是割点

当然如果是根节点也就是代码的$fa$,需要特判

如果根节点下面只有一个儿子说明不是割点,否则是

一旦发现割点就开始弹栈,但是不把当前割点弹出来(但仍然计算在当前的点双中)

因为一个割点包含在多个点双里面

void tarjan(int u,int fa){
   	int child=0;	dfn[u]=low[u]=++id,	stac[++top]=u;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v=d[i].to;		if( !dfn[v] )		{
   			tarjan(v,fa);			low[u]=min( low[v],low[u] );			if( low[v]>=dfn[u] )			{
   				child++;				if( u!=fa||child>=2 )	cut[u]=1;				bcc[++bccnum].clear();				while( stac[top]!=u )					bcc[bccnum].push_back( stac[top--] );			/*	int temp;				while( temp=stac[top--] )				{					bcc[bccnum].push_back(temp);					if( temp==v )	break;					}这是一样的写法*/				bcc[bccnum].push_back(u);//割点不能出栈,因为可能包含在多个点双里				 			}		}		else	low[u]=min( low[u],dfn[v] );	}}

完整代码

#include 
   
    using namespace std;const int maxn=2e5+10;int n,m,cut[maxn];struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt]=(edge){
   v,head[u]},head[u]=cnt;}int low[maxn],dfn[maxn],stac[maxn],top,id,dc;vector
    
     dcc[maxn];void tarjan(int u,int root){
   	dfn[u]=low[u]=++id,stac[++top]=u;	if( u==root&&!head[u] )//孤立点	{
   		dcc[++dc].push_back(u);		return;		} 	int flag=0;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v=d[i].to;		if( !dfn[v] )		{
   			tarjan(v,root);			low[u]=min( low[u],low[v] );			if( low[v]>=dfn[u] )//不通过u,v无法回到更浅的节点			{
   				flag++;				if( u!=root||flag>1 )	cut[u]=1;				int temp; ++dc;//发现割点,开始弹栈 				//注意,如果u是父节点且只有1个儿子,不算割点,但也会开始弹栈 				while( temp=stac[top--] )				{
   					dcc[dc].push_back(temp);					if( temp==v )	break;//直到遇到v 				}				dcc[dc].push_back(u);			}			}		else	low[u]=min(low[u],dfn[v] );	}}int main(){
   	cin >> n >> m;	for(int i=1;i<=m;i++)	{
   		int l,r; cin >> l >> r;		add(l,r); add(r,l);	}	for(int i=1;i<=n;i++)		if( !dfn[i] )	tarjan(i,i);	for(int i=1;i<=dc;i++)	{
   		for(int j=0;j
    
   

例题

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;const int mod = 998244353;struct edge{
    int to,nxt; }d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
    d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt; }int n,m;int dfn[maxn],low[maxn],cut[maxn],stac[maxn];int dc,top,id,child,root;vector
    
     dcc[maxn];void tarjan(int u,int fa){
   	dfn[u] = low[u] = ++id, stac[++top]=u;	if( u==root&&!head[u] )//孤立点	{
   		dcc[++dc].push_back(u);		return;		} 	int child=0;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v=d[i].to;		if( !dfn[v] )		{
   			tarjan(v,u);			low[u]=min( low[u],low[v] );			if( low[v]>=dfn[u] )//不通过u,v无法回到更浅的节点			{
   				child++;				int temp; ++dc;//发现割点,开始弹栈 				//注意,如果u是父节点且只有1个儿子,不算割点,但也会开始弹栈 				while( temp=stac[top--] )				{
   					dcc[dc].push_back(temp);					if( temp==v )	break;//直到遇到v 				}				dcc[dc].push_back(u);			}			}		else if( v!=fa )	low[u]=min(low[u],dfn[v] );	}	if( u==fa && child>=2 )	cut[u] = 1;}int quick(int x,int n){
   	int ans = 1;	for( ; n ; n>>=1,x=1ll*x*x%mod )		if( n&1 )	ans = 1ll*ans*x%mod;	return ans;}signed main(){
   	cin >> n >> m;	for(int i=1;i<=m;i++)	{
   		int l,r; scanf("%d%d",&l,&r);		add(l,r); add(r,l);	}	for(int i=1;i<=n;i++)		if( !dfn[i] )	tarjan(i,i);	int ans = 1,num = 0;	for(int i=1;i<=dc;i++)	{
   		if( dcc[i].size()>=3 )		{
   			num += dcc[i].size();			ans = 1ll*ans*( quick(2,dcc[i].size() )-1 )%mod;		}	}	ans = 1ll*ans*quick(2,m-num)%mod;	cout << ( ans%mod+mod )%mod;}/*11 131 21 3 2 43 44 54 66 77 85 88 98 1010 119 11*/
    
   

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