3693 - 家谱树
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
题目输入
第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
C++解答
#include<iostream> #include<cstring> using namespace std; int graph[100][100]; //邻接阵 int indegree[100]; //记录顶点的入度 int n; //n为顶点个数 int main() { memset(graph,0,sizeof(graph)); memset(indegree,0,sizeof(indegree)); cin>>n; int e; for(int i=1;i<=n;i++) { while(cin>>e) { if(e!=0) { graph[i][e]=1; indegree[e]++; continue; } else break; } } for(int i=1;i<=n;++i) //遍历n次每次找出一个顶点 { for(int j=1;j<=n;++j) //遍历所有的结点 { if(indegree[j]==0) { indegree[j]--; //该顶点的入度为-1，防止该顶点被在此遍历到，相当于删除。 cout<<j<<' '; for(int k=1;k<=n;++k) { if(graph[j][k]) indegree[k]--; //与该顶点关联的顶点的入度递减 } break; } } } //while (1); }