2367 Genealogical tree

問題概要

Martians族と会談するのに、ある人の祖先はある人の子孫よりも先に会談しなければならない。
人ごとに子供の番号のリストが与えられるとき、会談する順番を(どれか一通り)出力せよ。
そのような答えがあることは保証されている。


N≦100を満たす。

解法

トポロジカルソート。
トポロジカルソートは、グラフを深さ優先探索して、帰りがけに答えの配列に自分の番号をプッシュして行くというアルゴリズムによりできる。

ソースコード

int n; bool v[100];
vector<vi> e;
vi ans;
void rec(int c){
	v[c]=1;
	fr(i,e[c])if(!v[*i])rec(*i);
	ans.pb(c+1);
}
int main()
{
	scanf("%d",&n);
	e.resize(n);
	int a;
	rep(i,n)while(scanf("%d",&a),a)e[i].pb(a-1);
	
	rep(i,n)if(!v[i])rec(i);
	rep(i,n)printf("%d%c",ans[n-1-i],i==n-1?'\n':' ');
	return 0;
}