请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

图论--强连通分量

2023-07-13

描述

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

输入描述

多测试用例,每个测试用例:

第一行给出顶点数 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题,话不多说,上代码:

#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);
}

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部