[POJ] 2367 Genealogical tree.cpp

#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]);
    }
}