【图论】强连通分量-Toy模板网

这篇具有很好参考价值的文章主要介绍了【图论】强连通分量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.定义

【图论】强连通分量,图论,图论,算法,c++

强连通分量（Strongly Connected Components，简称SCC）是图论中的一个概念，用于描述有向图中的一组顶点，其中任意两个顶点之间都存在一条有向路径。换句话说，对于图中的任意两个顶点u和v，如果存在一条从u到v的有向路径，同时也存在一条从v到u的有向路径，那么u和v就属于同一个强连通分量。

强连通分量在许多图算法中都有重要的应用，比如强连通分量的计算可以用于解决图的可达性问题、强连通分量的缩点可以用于求解最小生成树等。

注意：强连通分量是有向图！

二.例题

P2863 [USACO06JAN] The Cow Prom S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

三.思路

我们可以易知可以求得环即可。也可以说要求有多少强连通分量。

这里可以用tarjan算法实现文章来源地址https://www.toymoban.com/news/detail-622035.html

四.参考代码

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
struct Edge{
	int u,v,next;
}edge[maxn];
int head[maxn],cnt;
void add(int u,int v){
	edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
int dfn[maxn],low[maxn],tot;
int sta[maxn],ins[maxn],num;
int ls;
int ans[maxn];
void tarjan(int u){
	dfn[u]=low[u]=++tot;
	sta[++num]=u;
	ins[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(dfn[v]==0){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if(ins[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	int j=0;
	if(dfn[u]==low[u]){
		ls++;
		do{
			ans[ls]++;
			j=sta[num--];
			ins[j]=0;
		}while(j!=u);
	}
}
int n,m,sum;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=ls;i++){
		if(ans[i]>1) sum++;
	} 
	cout<<sum;
	return 0;
}

到了这里，关于【图论】强连通分量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！