很裸的拓扑排序
1 /*
2 * File: 1022. Genealogical tree
3 * Author: xiaotian @ hnu
4 * Created on 2010年9月28日, 下午 9:26
5 * 解题：很裸的拓扑排序
6 */
7
8 #include<stdio.h>
9 #include<iostream>
10 #include<string.h>
11 #define N 108
12 using namespace std;
13 bool t[N][N];
14 int d[N];
15 int n;
16 void init()
17 {
18 memset(d,0,sizeof(d));
19 memset(t,0,sizeof(t));
20 for(int i=1;i<=n;i++)
21 for(int a;scanf("%d",&a) && (a>0);d[a]++)
22 t[i][a]=1;
23 }
24 void calc()
25 {
26 for(int dex=1;dex<=n;dex++)
27 {
28 int k=1;
29 for(;(k<=n)&&(d[k]>0);k++);
30 d[k]=1<<30-1;
31 for(int i=1;i<=n;i++) if(t[k][i]) d[i]--;
32 printf(dex==n?"%d\n":"%d ",k);
33 }
34 }
35 int main()
36 {
37 while(scanf("%d",&n)!=EOF)
38 {
39 init();
40 calc();
41 }
42 return 0;
43 }