POJ 2367 Genealogical tree

題意：
    第一行N表示有N個數(編號1~N)，接下來N行每行有幾個數字，第i行表示數字i需要在第i行那些數前面，例如Sample Input的4 5 1 0表示數字2需要在4,5,1的前面，以數字0代表該行的終止。

想法：
    建立graph，從起點(沒有其他點連入)開始用DFS走遍整個graph，並記下走過的順序，最後再逆向輸出就是一個topological sort。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int N;
	vector<int> children[101];
	int numOfElder[101];
	int visit[101];
	vector<int> Ans;
	void Initial()
	{
	Ans.clear();
	for (int i = 1; i <= N; ++i) {
	children[i].clear();
	numOfElder[i] = 0;
	visit[i] = 0;
	}
	}
	void DFS(int n)
	{
	if (visit[n] == 1) return; // 避免路徑變成一個環
	visit[n] = 1;
	for (int i = 0; i < children[n].size(); ++i)
	if (visit[children[n][i]] != 2)
	DFS(children[n][i]);
	visit[n] = 2; // 將這個node標記成已經走過
	Ans.push_back(n);
	}
	int main()
	{
	while (scanf("%d", &N) != EOF) {
	Initial();
	for (int i = 1; i <= N; ++i) {
	int member;
	while (scanf("%d", &member) && member != 0) {
	children[i].push_back(member);
	++numOfElder[member];
	}
	}
	for (int i = 1; i <= N; ++i)
	if (numOfElder[i] == 0)
	DFS(i);
	for (int i = Ans.size() - 1; i > 0; --i)
	printf("%d ", Ans[i]);
	printf("%d\n", Ans[0]);
	}
	}

view raw [POJ] 2367 Genealogical tree.cpp hosted with ❤ by GitHub