Genealogical tree. 家谱树 Time Limit: 1 second Memory Limit: 16M
Background 大意：火星人的种族关系比较混乱。宗族管理委员会进行开会发言等活动时，又想遵守先长辈，后晚辈的顺序。 于是有下面的问题：
Problem 编写一个程序对给定的人员，决定一个先后顺序， 这个顺序必须遵守先长辈，后晚辈的原则。
Input 首行为N， 1 <= N <= 100 ,N为总人数。根据百年传统，给人员用自然数编号为1至N。以下的N行，第I行为第I个人的子孙列表，子孙的顺序是任意的，用空格隔开，且以0为结束。子孙列表可以是空的。
Output 在一行内输出发言的顺序。 如有多个顺序满足条件，则输出任一个。至少会有一个满足的顺序的。
Sample Input
5 0 4 5 1 0 1 0 5 3 0 3 0
Sample Output
2 4 5 3 1
/* URAL 1022 Genealogical tree
* 900803 09:04:18 21 Aug 2005 RoBa 1022 C++ Accepted 0.001 190 KB
* 拓扑排序
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int MAX = 101;
int map[MAX][MAX],inde[MAX],taken[MAX];
int main()
{
int i,n,tmp,j;
while (scanf("%d",&n)!=EOF)
{
memset(map,0,sizeof(map));
memset(inde,0,sizeof(inde));
for (i = 1 ; i <= n ; i++)
while (scanf("%d",&tmp),tmp)
{
map[i][tmp] = 1;
++inde[tmp];
}
while (1)
{
for (i = 1 ; i <= n ; i++)
if (inde[i] == 0 && taken[i] == 0) break;
if (i > n) break;
for (j = 1 ; j <= n ; j++)
if (map[i][j])
{
map[i][j] = 0;
--inde[j];
}
taken[i] = 1;
printf("%d ",i);
}
printf("\n");
}
return 0;
}
posted on 2011-10-06 19:19
nk_ysg 阅读(305)
评论(0) 编辑 收藏 引用 所属分类:
算法