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