Genealogical tree. 家譜樹 Time Limit: 1 second Memory Limit: 16M
Background 大意：火星人的種族關系比較混亂。宗族管理委員會進行開會發(fā)言等活動時，又想遵守先長輩，后晚輩的順序。 于是有下面的問題：
Problem 編寫一個程序?qū)o定的人員，決定一個先后順序， 這個順序必須遵守先長輩，后晚輩的原則。
Input 首行為N， 1 <= N <= 100 ,N為總?cè)藬?shù)。根據(jù)百年傳統(tǒng)，給人員用自然數(shù)編號為1至N。以下的N行，第I行為第I個人的子孫列表，子孫的順序是任意的，用空格隔開，且以0為結(jié)束。子孫列表可以是空的。
Output 在一行內(nèi)輸出發(fā)言的順序。 如有多個順序滿足條件，則輸出任一個。至少會有一個滿足的順序的。
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 閱讀(329)
評論(0) 編輯 收藏 引用 所屬分類:
算法