【问题描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。 输出一个序列，使得每个人的后辈都比那个人后列出。
【输入格式】
第1行一个整数N（1<=N<=100），表示家族的人数。 接下来N行，第i行描述第i个人的儿子。 每行最后是0表示描述完毕。
【输出格式】
输出一个序列，使得每个人的后辈都比那个人后列出。 如果有多解输出任意一解。
【输入样例】
5 0 4 5 1 0 1 0 5 3 0 3 0
【输出样例】
2 4 5 3 1
拓扑排序算法
【stack】
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int a[101][101],c[101],r[101],ans[101]; 5 int i,j,tot,temp,num,n,m; 6 int main() 7 { 8 cin >> n; 9 for (i = 1; i <= n; i++) 10 { 11 do 12 { 13 cin >> j; 14 if (j !=0 ) 15 { 16 c[i]++; //c[i]用来存点i的出度 计数 17 a[i][c[i]] = j; 18 r[j]++; //r[j]用来存点j的入度。 19 } 20 } 21 while (j != 0); 22 } 23 for (i = 1; i <= n; i++) 24 if (r[i] == 0) 25 ans[++tot] = i; //把图中所有入度为0的点入栈，栈用一维数组ans[]表示 26 do 27 { 28 temp = ans[tot]; 29 cout << temp << " "; 30 tot--; num++; //栈顶元素出栈并输出 31 for (i = 1; i <= c[temp]; i++) 32 { 33 r[a[temp][i]]--; 34 if (r[a[temp][i]] == 0) //如果入度减1后变成0，则将这个后继点入栈 35 ans[++tot] = a[temp][i]; 36 } 37 } 38 while (num != n); //tot>0 //如果输出的点的数目num等于n，说明算法结束 39 return 0; 40 }
【Vector + queue】
