http://acm.timus.ru/problem.aspx?space=1&num=1022
拓扑排序
1 #include <iostream>
2 using namespace std;
3 int n;
4 int link[111][111];
5 int ru[111];
6 int q[111],st,en;
7 bool v[111];
8 int fn,flist[111];
9 bool first=true;
10
11 void del(int x){
12 for (int i=1;i<=link[x][0];++i){
13 --ru[link[x][i]];
14 }
15 }
16
17 void ou(int x){
18 del(x);
19 if (first){
20 printf("%d",x);
21 first=false;
22 }
23 else printf(" %d",x);
24 }
25
26 void find(){
27 fn=0;
28 for (int i=1;i<=n;++i) if (!v[i]&&ru[i]==0){
29 v[i]=true;
30 flist[++fn]=i;
31 }
32 }
33
34 int main(){
35 scanf("%d",&n);
36 for (int i=1;i<=n;++i){
37 int x;
38 scanf("%d",&x);
39 while (x!=0){
40 link[i][++link[i][0]]=x;
41 ++ru[x];
42 scanf("%d",&x);
43 }
44 }
45 find();
46 while (fn>0){
47 for (int i=1;i<=fn;++i) ou(flist[i]);
48 find();
49 }
50 }
51
posted on 2008-11-04 10:25
Joseph 阅读(124)
评论(0) 编辑 收藏 引用