登录
← 返回首页 | 代码片段 › 3 图论 › 3.3 图的连通性 › 图的连通性 / 搜索
JSON MD

3.3 图的连通性

拓扑排序 add
31 行
CPP JSON
【拓扑排序】 拓扑排序模板,基于 Kahn 算法或 DFS。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 核心结构体:QAQ 关键配置: N=5003,M=5e5+3,inf=2e9,P=80112002 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 30 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=5e5+3,inf=2e9,P=80112002;
int n,m,x,y,o,ans,dp[N],ru[N],chu[N],head[N];
struct QAQ{int to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}

int main(){
	in(n),in(m);
	while(m--)in(x),in(y),add(x,y),++ru[y],++chu[x];
	for(Re i=1;i<=n;++i)if(!ru[i])dp[i]=1,Q.push(i);
	while(!Q.empty()){
		Re x=Q.front();Q.pop();
		for(Re i=head[x],to;i;i=a[i].next){
			(dp[to=a[i].to]+=dp[x])%=P;
			if(!--ru[to])Q.push(to);
		}
	}
	for(Re i=1;i<=n;++i)if(!chu[i])(ans+=dp[i])%=P;
	printf("%d\n",ans%P);
}
2-SAT kosaraju
44 行
CPP JSON
【2-SAT(kosaraju)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs1(Re x) — 深度优先搜索遍历 void dfs2(Re x) — 深度优先搜索遍历 void kosaraju(无参数) — 后缀数组 核心结构体:Kosaraju, QAQ 关键配置: N=2e6+3,M=2e6+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 43 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=2e6+3,M=2e6+3;
int n,m,mm,p1,p2,x1,x2,Q_o,X[M],Y[M],ip[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Kosaraju{
	int o,ndfn_o,nQ[N],pan[N],head[N];
	struct QAQ{int x,to,next;}a[M];
	inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs1(Re x){
		pan[x]=1;
		for(Re i=head[x];i;i=a[i].next)if(!pan[a[i].to])dfs1(a[i].to);
		nQ[++ndfn_o]=x;
	}
	inline void dfs2(Re x){
		ip[x]=Q_o;
		for(Re i=head[x];i;i=a[i].next)if(!ip[a[i].to])dfs2(a[i].to);
	}
	inline void kosaraju(){
		for(Re i=1;i<=m;++i)add(X[i],Y[i]);
		for(Re i=1;i<=2*n;++i)if(!pan[i])dfs1(i);
		memset(head,0,sizeof(head));
		memset(pan,0,sizeof(pan));
		memset(a,0,sizeof(a));o=0;
		for(Re i=1;i<=m;++i)add(Y[i],X[i]);
		for(Re i=ndfn_o;i;--i)if(!ip[nQ[i]])++Q_o,dfs2(nQ[i]);
	}
}T1;
int main(){
	in(n),in(mm);
	while(mm--)in(p1),in(x1),in(p2),in(x2),X[++m]=p1+(x1^1)*n,Y[m]=p2+x2*n,X[++m]=p2+(x2^1)*n,Y[m]=p1+x1*n;
	T1.kosaraju();
	for(Re i=1;i<=n;++i)if(ip[i]==ip[i+n])return !printf("IMPOSSIBLE");
	puts("POSSIBLE");
	for(Re i=1;i<=n;++i)printf("%d ",ip[i]<ip[i+n]);
}
2-SAT tarjan
40 行
CPP JSON
【2-SAT(tarjan)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x) — Tarjan算法(求SCC/LCA/割点桥) void SuoPoint(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ 关键配置: N=2e6+3,M=2e6+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 40 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=2e6+3,M=2e6+3;
int n,m,p1,p2,x1,x2,Q_o,ip[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Tarjan{
	int o,t,dfn_o,Q[N],low[N],dfn[N],pan[N],head[N];
	struct QAQ{int to,next;}a[M];
	inline int min(Re a,Re b){return a<b?a:b;}
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x){
		low[x]=dfn[x]=++dfn_o,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
			else if(pan[to])low[x]=min(low[x],dfn[to]);
		if(low[x]==dfn[x]){
			++Q_o;
			while(1){
				ip[Q[t]]=Q_o,pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void SuoPoint(){for(Re i=1;i<=2*n;++i)if(!dfn[i])tarjan(i);}
}T1;
int main(){
	in(n),in(m);
	while(m--)in(p1),in(x1),in(p2),in(x2),T1.add(p1+(x1^1)*n,p2+x2*n),T1.add(p2+(x2^1)*n,p1+x1*n);
	T1.SuoPoint();
	for(Re i=1;i<=n;++i)if(ip[i]==ip[i+n])return !printf("IMPOSSIBLE");
	puts("POSSIBLE");
	for(Re i=1;i<=n;++i)printf("%d ",ip[i]>ip[i+n]);
}
割点 tanjan min
39 行
CPP JSON
【割点 tanjan】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x,Re root) — Tarjan算法(求SCC/LCA/割点桥) void cut_point(无参数) — 核心算法函数 核心结构体:Cut_Point, QAQ 关键配置: N=2e4+3,M=2e5+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=2e4+3,M=2e5+3;
int n,m,x,y,ans,cut[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Cut_Point{
	int o,dfn_o,low[N],dfn[N],head[N];
	struct QAQ{int to,next;}a[M];
	inline int min(Re a,Re b){return a<b?a:b;}
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x,Re root){
		Re son=0;dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,root),++son;
				low[x]=min(low[x],low[to]);
				cut[x]|=(x!=root&&low[to]>=dfn[x]);
			}
			else low[x]=min(low[x],dfn[to]);
		cut[x]|=(x==root&&son>1),ans+=cut[x];
	}
	inline void cut_point(){
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,i);
	}
}T1;
int main(){
	in(n),in(m);
	while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	T1.cut_point();
	printf("%d\n",ans);
	for(Re i=1;i<=n;++i)if(cut[i])printf("%d ",i);
}
割边,桥 旅游航道
45 行
CPP JSON
【割边,桥(旅游航道)】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void CL(无参数) — 核心算法函数 void tarjan(Re x,Re p) — Tarjan算法(求SCC/LCA/割点桥) void get_bridg(无参数) — 获取值 核心结构体:Tarjan, QAQ 关键配置: N=3e4+3,M=3e4+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 44 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=3e4+3,M=3e4+3;
int n,m,x,y,ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Tarjan{
	int o,dfn_o,dfn[N],low[N],head[N],bridge[M<<1];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void CL(){
		memset(bridge,0,sizeof(bridge));
		memset(head,0,sizeof(head));
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		dfn_o=ans=0,o=1;
	}
	inline void tarjan(Re x,Re p){
		dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,i);
				low[x]=min(low[x],low[to]);
				if(low[to]>dfn[x])bridge[i]=bridge[i^1]=1,++ans;
			}
			else if(i!=(p^1))low[x]=min(low[x],dfn[to]);
	}
	inline void get_bridg(){for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,-1);}
}T1;
int main(){
    while(scanf("%d%d",&n,&m)&&n&&m){
	    T1.CL();
	    while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	    T1.get_bridg();
	    printf("%d\n",ans);
    }
}
欧拉回路 (Hierholzer) 无向+有向
63 行
CPP JSON
【欧拉回路 (Hierholzer)(无向+有向)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 核心结构体:Euler_Circle__Undirected_Graph, QAQ, Euler_Circle__Directed_Graph, QAQ 关键配置: N=1e5+3,M=2e5+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=1e5+3,M=2e5+3;
int n,m,x,y,m_,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Euler_Circle__Undirected_Graph{// 无向图欧拉路
	int o,du[N],cur[N],ans[M],pan[M<<1],head[N];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		for(Re i=head[x];i;i=head[x]){
			head[x]=a[i].next;// 当前弧优化
			if(!pan[i]){
				pan[i]=pan[i^1]=1;
				dfs(a[i].to);
				ans[++ans[0]]=(i&1)?-i/2:i/2;
			}
		}
	}
	inline void sakura(){
		in(n),in(m),m_=m,o=1;
		while(m_--)in(x),in(y),add(x,y),add(y,x),++du[x],++du[y];
		for(Re i=1;i<=n;cur[i]=head[i],++i)if(du[i]&1){puts("NO");return;}
		for(Re i=1;i<=n;++i)if(du[i]){dfs(i);break;}
		if(ans[0]!=m){puts("NO");return;}
		puts("YES");
		for(Re i=ans[0];i>=1;--i)printf("%d ",ans[i]);
	}
}T1;
struct Euler_Circle__Directed_Graph{// 无向图欧拉路
	int o,ru[N],chu[N],cur[N],ans[M],head[N];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		for(Re i=head[x];i;i=head[x]){
			head[x]=a[i].next;// 当前弧优化
			dfs(a[i].to);
			ans[++ans[0]]=i;
		}
	}
	inline void sakura(){
		in(n),in(m),m_=m;
		while(m_--)in(x),in(y),add(x,y),++ru[y],++chu[x];
		for(Re i=1;i<=n;cur[i]=head[i],++i)if(ru[i]!=chu[i]){puts("NO");return;}
		for(Re i=1;i<=n;++i)if(chu[i]){dfs(i);break;}
		if(ans[0]!=m){puts("NO");return;}
		puts("YES");
		for(Re i=ans[0];i>=1;--i)printf("%d ",ans[i]);
	}
}T2;
int main(){
	in(op);
	if(op==1)T1.sakura();
	if(op==2)T2.sakura();
}
欧拉路,欧拉回路 骑马修栅栏
29 行
CPP JSON
【欧拉路,欧拉回路(骑马修栅栏)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 void dfs(Re x) — 深度优先搜索遍历 关键配置: N=1030 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 28 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1030;
int n,x,y,mi=2e9,st=2e9,as,du[N],ans[N],r[N][N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void dfs(Re x){
	for(Re i=1;i<=500;++i)
		if(r[x][i]){
			--r[x][i],--r[i][x];
			dfs(i);
		}
	ans[++as]=x;
}
int main(){
	in(n);
	for(Re i=1;i<=n;++i)in(x),in(y),++r[x][y],++r[y][x],++du[x],++du[y],mi=min(mi,min(x,y));
	for(Re i=1;i<=500;++i)if(du[i]&1)st=min(st,i);
	if(st==2e9)st=mi;
	dfs(st);
	for(Re i=as;i;--i)printf("%d\n",ans[i]);
}
缩点—强联通分量 Kosaraju
67 行
CPP JSON
【缩点—强联通分量(Kosaraju)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs1(Re x) — 深度优先搜索遍历 void dfs2(Re x) — 深度优先搜索遍历 void kosaraju(无参数) — 后缀数组 void add(Re x,Re y) — 加法更新 void creat(无参数) — 核心算法函数 核心结构体:Kosaraju, QAQ, Tuopu, QAQ 关键配置: N=1e6+3,M=1e6+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 66 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
const int N=1e6+3,M=1e6+3;
int n,m,Q_o,ans,X[M],Y[M],A[N],ip[N],gs[N],dp[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct Kosaraju{
	int o,ndfn_o,nQ[N],pan[N],head[N];
	struct QAQ{int x,to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs1(Re x){
		pan[x]=1;
		for(Re i=head[x];i;i=a[i].next)if(!pan[a[i].to])dfs1(a[i].to);
		nQ[++ndfn_o]=x;
	}
	inline void dfs2(Re x){
		ip[x]=Q_o,gs[Q_o]+=A[x];
		for(Re i=head[x];i;i=a[i].next)if(!ip[a[i].to])dfs2(a[i].to);
	}
	inline void kosaraju(){
		for(Re i=1;i<=m;++i)add(X[i],Y[i]);
		for(Re i=1;i<=n;++i)if(!pan[i])dfs1(i);
		memset(head,0,sizeof(head));
		memset(pan,0,sizeof(pan));
		memset(a,0,sizeof(a));o=0;
		for(Re i=1;i<=m;++i)add(Y[i],X[i]);
		for(Re i=ndfn_o;i;--i)if(!ip[nQ[i]])++Q_o,dfs2(nQ[i]);
	}
}T1;
struct Tuopu{
	int o,x,y,ru[N],pan[N],head[N];std::queue<int>Q;
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void creat(){
		for(Re i=1;i<=T1.o;++i)
			if((x=ip[T1.a[i].x])!=(y=ip[T1.a[i].to]))
				++ru[y],add(x,y);
	}
	inline void tuopu(){
		creat();
		for(Re i=1;i<=Q_o;++i)if(!ru[i])dp[i]=gs[i],Q.push(i);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			for(Re i=head[x],to;i;i=a[i].next){
				to=a[i].to;
				dp[to]=max(dp[to],dp[x]+gs[to]);
				if(!(--ru[to]))Q.push(to);
			}
		}
	}
}T2;
int main(){
	in(n),in(m);
	for(Re i=1;i<=n;++i)in(A[i]);
	for(Re i=1;i<=m;++i)in(X[i]),in(Y[i]);
	T1.kosaraju(),T2.tuopu();
	for(Re i=1;i<=Q_o;++i)ans=max(ans,dp[i]);
	printf("%d",ans);
}
缩点—强联通分量 Tarjan
63 行
CPP JSON
【缩点—强联通分量(Tarjan)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x) — Tarjan算法(求SCC/LCA/割点桥) void SuoPoint(无参数) — 核心算法函数 void add(Re x,Re y) — 加法更新 void creat(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ, Tuopu, QAQ 关键配置: N=1e4+3,M=1e5+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 62 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
const int N=1e4+3,M=1e5+3;
int n,m,x,y,Q_o,ans,A[N],ru[N],gs[N],ip[N],dp[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int min(Re a,Re b){return a<b?a:b;}
inline int max(Re a,Re b){return a>b?a:b;}
struct Tarjan{
	int o,t,dfn_o,Q[N],low[N],dfn[N],pan[N],head[N];
	struct QAQ{int x,to,next;}a[M];
	inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x){
		dfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
			else if(pan[to])low[x]=min(low[x],dfn[to]);
		if(low[x]==dfn[x]){
			++Q_o;
			while(1){
				ip[Q[t]]=Q_o,gs[Q_o]+=A[Q[t]],pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void SuoPoint(){for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);}
}T1;
struct Tuopu{
	int o,ru[N],pan[N],head[N];std::queue<int>Q;
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void creat(){
		for(Re i=1;i<=T1.o;++i)
			if((x=ip[T1.a[i].x])!=(y=ip[T1.a[i].to]))
				++ru[y],add(x,y);
	}
	inline void tuopu(){
		for(Re i=1;i<=Q_o;++i)if(!ru[i])dp[i]=gs[i],Q.push(i);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			for(Re i=head[x],to;i;i=a[i].next){
				to=a[i].to;
				dp[to]=max(dp[to],dp[x]+gs[to]);
				if(!(--ru[to]))Q.push(to);
			}
		}
	}
}T2;
int main(){
	in(n),in(m);
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),T1.add(x,y);
	T1.SuoPoint(),T2.creat(),T2.tuopu();
	for(Re i=1;i<=Q_o;++i)ans=max(ans,dp[i]);
	printf("%d",ans);
}
缩点—点双连通分量 矿场搭建
65 行
CPP JSON
【缩点—点双连通分量(矿场搭建)】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void CL(无参数) — 核心算法函数 void tarjan(Re x,Re rt) — Tarjan算法(求SCC/LCA/割点桥) void SuoPoint(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ 关键配置: N=1003,M=503 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 64 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,M=503;
int n,m,x,y,T,Q_o,tmp,ans1,cut[N];LL ans2;
std::vector<int>dcc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct Tarjan{
	int o,t,dfn_o,Q[N],dfn[N],low[N],head[N];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void CL(){
		memset(head,0,sizeof(head));
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		memset(cut,0,sizeof(cut));
		dfn_o=t=o=0;
	}
	inline void tarjan(Re x,Re rt){
		Re son=0;Q[++t]=x,dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,rt),++son;
				low[x]=min(low[x],low[to]);
				if(low[to]>=dfn[x]){
					if(x!=rt)cut[x]=1;
					else cut[x]|=son>1;
					++Q_o;
					while(1){
						dcc[Q_o].push_back(Q[t]);
						if(to==Q[t--])break;
					}
					dcc[Q_o].push_back(x);
				}
			}
			else low[x]=min(low[x],dfn[to]);
	}
	inline void SuoPoint(){for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,i);}
}T1;
int main(){
    while(scanf("%d",&m)&&m){
	    for(Re i=1;i<=Q_o;++i)dcc[i].clear();
	    T1.CL(),Q_o=ans1=n=0,ans2=1;
	    while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x),n=max(n,max(x,y));
	    T1.SuoPoint();
	    for(Re i=1;i<=Q_o;++i){
	    	tmp=0,n=dcc[i].size();
	    	for(Re j=0;j<n;++j)tmp+=cut[dcc[i][j]];
	    	if(!tmp)ans1+=2,ans2*=(n-1)*n/2;
	    	else if(tmp<2)ans1+=1,ans2*=(n-1);
	    }
	    printf("Case %d: %d %lld\n",++T,ans1,ans2);
    }
}
缩点—边双连通分量 Redundant Paths
46 行
CPP JSON
【缩点—边双连通分量(Redundant Paths)】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x,Re p) — Tarjan算法(求SCC/LCA/割点桥) void dfs(Re x) — 深度优先搜索遍历 void SuoPoint(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ 关键配置: N=5003,M=10003 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 45 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=10003;
int n,m,x,y,Q_o,leaf,ip[N],du[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Tarjan{
	int o,dfn_o,dfn[N],low[N],head[N],bridge[M<<1];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x,Re p){
		dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,i);
				low[x]=min(low[x],low[to]);
				if(low[to]>dfn[x])bridge[i]=bridge[i^1]=1;
			}
			else if(i!=(p^1))low[x]=min(low[x],dfn[to]);
	}
	inline void dfs(Re x){
		ip[x]=Q_o;
		for(Re i=head[x];i;i=a[i].next)
			if(!ip[a[i].to]&&!bridge[i])dfs(a[i].to);
	}
	inline void SuoPoint(){
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,-1);
		for(Re i=1;i<=n;++i)if(!ip[i])++Q_o,dfs(i);
	}
}T1;
int main(){
    in(n),in(m),T1.o=1;
    while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
    T1.SuoPoint();
    for(Re i=2;i<=T1.o;i+=2)
    	if((x=ip[T1.a[i].to])!=(y=ip[T1.a[i^1].to]))++du[x],++du[y];
    for(Re i=1;i<=Q_o;++i)leaf+=(du[i]==1);
    printf("%d",leaf+1>>1);
}
已复制