第三天也没标题

时间:2022-03-31 20:51:58


家谱树

【问题描述】

    有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。

    给出每个人的孩子的信息。

    输出一个序列,使得每个人的后辈都比那个人后列出。

【输入格式】

    1行一个整数N1<=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]);
  }
 }