1520.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1520 on 2006-04-18 at 06:45:36 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int VN = 5120;

class Graph {
private:
	vector<int> nei[VN];
	int v, dfn[VN], low[VN], id[VN];
	int stack[VN], top, cnt, scnt;
	void scR(int);
public:
	bool build();
	void bottom();
};
void Graph::scR(int u) {
	int i, h = low[u] = dfn[u] = cnt++;
	stack[top++] = u;
	for(i = 0; i < (int)nei[u].size(); i++) {
		int o = nei[u][i];
		if(dfn[o] == -1) scR(o);
		h = min(h, low[o]);
	}
	if(h < dfn[u]) low[u] = h;
	else {
		int k;
		do {
			k = stack[--top];
			id[k] = scnt; low[k] = VN;
		} while(k != u);
		scnt++;
	}
}
bool Graph::build() {
	scanf("%d", &v);
	if(v == 0) return false;
	int e, i; scanf("%d", &e);
	for(i = 0; i < v; i++) nei[i].clear();
	for(i = 0; i < e; i++) {
		int a, b; scanf("%d %d", &a, &b);
		nei[a-1].push_back(b-1);
	}
	memset(dfn, -1, sizeof(dfn));
	top = cnt = scnt = 0;
	return true;
}
void Graph::bottom() {
	int i, j;
	bool bot[VN]; memset(bot, true, sizeof(bot));
	for(i = 0; i < v; i++)
		if(dfn[i] == -1) scR(i);
	for(i = 0; i < v; i++)
		for(j = 0; j < (int)nei[i].size(); j++)
			if(id[i] != id[nei[i][j]]) bot[id[i]] = false;
	for(i = j = 0; i < v; i++)
		if(bot[id[i]]) { printf("%s%d", (j == 0 ? "" : " "), i+1); j++; }
	putchar('\n');
}

int main()
{
	Graph g;
	
	while(g.build()) g.bottom();
	
	return 0;
}