strongcoment.cpp

来自「求有向图的强连通分量」· C++ 代码 · 共 49 行

#include <iostream>
using namespace std;

#define maxn 1024


int g[maxn][maxn], n, mk[maxn], list[maxn], num;

void back(int u)
{
	mk[u]=1; 
	cout << u << " ";
	for(int v=1; v<=n; v++) 
		if(!mk[v] && g[v][u]) back(v);
}
void dfs(int u)
{ 
	mk[u]=1;
	for(int v=1; v<=n; v++) 
		if(!mk[v] && g[u][v]) dfs(v);
	list[num--] = u;
}
int main()
{
	int i, j, k, l;
	cin>>n; 
	for(i=1; i<=n; i++) 
		for(j=1; j<=n; j++) 
			cin >> g[i][j];
	memset(mk, 0, sizeof(mk));
	num = n;
	for(i=1; i<=n; i++) 
		if(!mk[i]) 
			dfs(i);
	memset(mk, 0, sizeof(mk));
	for(i=1; i<=n; ++i)
		cout << list[i] << endl;
	for(i=1; i<=n; i++)
		if(!mk[list[i]]) 
		{ 
			back(list[i]);
			cout << endl; 
		}

	cin >> j; //pause
	return 0 ;

}