家谱树
【问题描述】
有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列,使得每个人的后辈都比那个人后列出。
【输入格式】
第1行一个整数N(1<=N<=100),表示家族的人数。
接下来N行,第I行描述第I个人的儿子。
每行最后是0表示描述完毕。
【输出格式】
输出一个序列,使得每个人的后辈都比那个人后列出。
如果有多解输出任意一解。
【输入样例】
5
0
45 1 0
10
53 0
30
【输出样例】
24 5 3 1
应该是个很标准的拓扑排序的题目,题目给了个有向无环图,即AOV网。先选择入度为0的定点输出,再删除此顶点有关的边,一直循环到不存在入度为0的顶点为止(可设置一个栈,入一个出一个)。若最后结果顶点数小于AOV网中顶点数,则说明有回路。由于存在一个顶点的几个边权值可能相同的问题,所以答案可能不唯一。
while(top!=0)
{
out();
for(i=1;i<=bj[a];i++)
{
indgr[father[a][i]]--;
if(indgr[father[a][i]]==0) in(father[a][i]);
}
}