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

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

描述

给出一个有向图，求该图的强连通分量的个数。

输入描述

多测试用例，每个测试用例：

第一行给出顶点数 n ( 1 ≤ n ≤ 1000 )

第二行给出边数 e ( 0 ≤ e ≤ 100000 )

第三行开始，共 e 行，每行两个正整数 a b，表示从顶点 a 发出一条弧到顶点 b 。

输出描述

每个测试用例一行结果，一个正整数：该有向图的强连通分量的个数。

关于这道题，首先我们要知道什么是强连通分量：（from百度）有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

一道简单的oj题，话不多说，上代码：文章来源地址https://www.toymoban.com/news/detail-538887.html

#include<stack>
#include<cstring>
#include<iostream>
using namespace std;
stack<int> s;
int b[1005];//判断结点有没有走
int a[1005][1005],a1[1005][1005];//邻接矩阵
void init(int m);
void jisuan1(int t,int n);
void jisuan2(int t,int n); 
int main(){
	int n,m;//结点数，边数
	while(scanf("%d\n%d",&n,&m)!=EOF){
		init(m);
		while(!s.empty())
       		s.pop();
		memset(b,0,sizeof(b));	
		int i,sum=0;//sum为强连通量的个数 
		for(i=1;i<n+1;i++)
			if(b[i]==0) jisuan1(i,n);
		memset(b,0,sizeof(b));
		while(!s.empty()){
			int t;
			t=s.top();
			s.pop();
			if(b[t]==0){
				sum++;
				jisuan2(t,n);
			}
		}
		cout<<sum<<endl;
	} 
	return 0;
} 
void init(int m){
	//初始化两个邻接矩阵 
	memset(a,0,sizeof(a));
	memset(a1,0,sizeof(a1));
	int i,a2,b2;
	for(i=1;i<m+1;i++){
		cin>>a2>>b2;
	    a[a2][b2]=1;
		a1[b2][a2]=1;		
	 }
}
void jisuan1(int t,int n){
	int i;
	b[t]=1;
	for(i=1;i<n+1;i++)
		if(a[t][i]==1&&b[i]==0)
			jisuan1(i,n);
	s.push(t);
}
void jisuan2(int t,int n){
	int i;
	b[t]=1;
	for(i=1;i<n+1;i++)
		if(a1[t][i]==1&&b[i]==0)
			jisuan2(i,n);
}

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