the bottom of a graph(强连通分量).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 5100;
int v, e;
vector<int> path[MAX];
vector<int> npath[MAX];
int vis[MAX], scc, step;
int order[MAX], order_pos, id[MAX];

void dfs(int pos)
{
	int i,j,l;
	vis[pos] = true;
	l = path[pos].size();
	for (i=0;i<l;i++) {
		j = path[pos][i];
		if (!vis[j]) {
			dfs(j);
		}
	}
	order[ order_pos ++ ] = pos;//make order
}

void ndfs(int pos)
{
	int i,j,l;
	vis[pos] = true;
	id[pos] = scc;
	l = npath[pos].size();
	for (i=0;i<l;i++) {
		j = npath[pos][i];
		if (!vis[j]) {
			ndfs(j);
		}
	}
}

void Kosaraju()
{
	int i,j;
	//dfs in original graph
	memset(vis, 0, sizeof(vis));
	order_pos = 0;
	for (i=1; i<=v ;i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	//dfs in inverse graph
	memset(vis, 0, sizeof(vis));
	memset(id, 0, sizeof(id));
	scc = 1;
	for (i=order_pos-1; i>=0 ;i--) {
		if (!vis[ order[i] ]) {
			ndfs(order[i]);
			scc ++;
		}
	}
	scc --;
}

int main() {
	int i,j;
	while(scanf("%d", &v), v) {
		scanf("%d", &e);
		for(i=0;i<=v;i++) {
			path[i].clear();
			npath[i].clear();
		}
		while(e --) {
			int x,y;
			scanf("%d %d", &x,&y);
			path[x].push_back(y);
			npath[y].push_back(x);
		}
		Kosaraju();
		memset(vis, true, sizeof(vis));
		// If an edge leave the SCC, its source is not a sink.
		// 和最高强连通分量相反，sink 是最低强连通分量 
		for(i=1;i<=v;i++) {
			for(j=0;j<path[i].size();j++) {
				if(id[i] != id[ path[i][j] ]) {
					vis[ id[i] ] = false;
					break;
				}
			}
		}
		bool flag = false;
		for(i=1;i<=v;i++) {
			if(vis[ id[i] ]) {
				if(flag) putchar(' ');
				printf("%d", i);
				flag = true;
			}
		}
		puts("");
	}
}