qiangliantong.cpp

一个强联通算法的实现,时间复杂度很低,是很高效的算法

#include <iostream>
#include <string.h>
using namespace std;

int a[100][100];
int ca[100][100];
int na[100];
int nca[100];
int N,E;
int ord[100];
int r[100];
char v[100];
int t;

void GetOrder(int i)
{
	v[i] = 1;
	for(int j=0;j<na[i];j++) if (!v[a[i][j]])
	{
		GetOrder(a[i][j]);
	}
	ord[t++] = i;
}

void Color(int i)
{
	v[i] = 1;
	for(int j=0;j<nca[i];j++) if (!v[ca[i][j]])
	{
		Color(ca[i][j]);
	}
	r[i] = t;
}


int main()
{
	int i,j,k;
	memset(na,0,sizeof na);
	memset(nca,0,sizeof nca);
	cin>>N>>E;
	for(i=0;i<E;i++) 
	{
		cin>>j>>k;
		--j;--k;
		a[j][na[j]] = k;
		ca[k][nca[k]] = j;	
		na[j]++;
		nca[k]++;
	}
	memset(v,0,sizeof v);
	t = 0;
	for(i=0;i<N;i++) if (!v[i]) GetOrder(i);
	t = 0;
	memset(v,0,sizeof v);
	for(i=N-1;i>=0;i--) if (!v[ord[i]]) 
	{
		Color(ord[i]);
		t++;
	}
	for(i=0;i<N;i++) cout<<r[i]<<endl;
	return 0;
}
/*
7 10
7 1
7 6
1 2
2 3
3 2
2 4
4 1
4 5
5 6
6 5

*/