数据加载中……

URAL 1022 Genealogical tree

拓扑排序是最直接的算法.
 1 /* 拓扑排序 */
 2 
 3 #include<iostream>
 4 #include<vector>
 5 using namespace std;
 6 const int MAXN=120;
 7 vector<int> adj[MAXN];
 8 
 9 int into[MAXN];
10 
11 int main()
12 {
13   //freopen("data.in","r",stdin);
14   //freopen("data.out","w",stdout);
15   int n;
16   memset(into,0,sizeof(into));
17   cin >> n;
18   for (int i=1;i<=n;++i)
19     {
20       int x;
21       cin >> x;
22       while (x!=0
23     {
24       adj[i].push_back(x);
25       ++into[x];
26       cin >> x;
27     }
28     }
29  //for (int i=1;i<=n;++i) cout << into[i] << ' '; cout << endl;
30   bool everp=0;
31   for (int k=0;k<n;++k)
32     {
33       int i=1;
34       for (;i<=n;i++if (!into[i]) break;
35       (everp) ? cout << ' ' << i : cout << i;
36       everp=1;
37       --into[i];
38       for (int j=0;j<adj[i].size();++j) --into[ adj[i][j] ];
39     }
40   cout << endl;
41   return 0;
42 }
43 


posted on 2009-07-21 17:14 Chen Jiecao 阅读(171) 评论(0)  编辑 收藏 引用 所属分类: URAL


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理