UVa 10305 Ordering Tasks【拓扑排序】

浏览数：31 / 时间：2015年06月08日

题意：给出n件事情，m个二元组关系，求它们的拓扑序列

用的队列来做

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
14 
15 typedef long long LL;
16 const int INF = (1<<30)-1;
17 const int mod=1000000007;
18 const int maxn=100005;
19 int ecnt;
20 int n,m;
21 
22 int g[1005][1005],in[1005],ans[maxn];
23 
24 void toposort(){
25     queue<int> q;
26     
27     for(int i=1;i<=n;i++)
28     if(in[i]==0) q.push(i);
29     
30     int cnt=0;
31     while(!q.empty()){
32         int tmp=q.front();q.pop();
33         ans[++cnt]=tmp;
34         
35         for(int j=1;j<=n;j++){
36             if(g[tmp][j]){
37                 in[j]--;
38                 if(in[j]==0) q.push(j);
39             }
40         }        
41     }
42     
43     printf("%d",ans[1]);
44     for(int i=2;i<=cnt;i++)
45     printf(" %d",ans[i]);    
46     printf("\n");
47 }
48 
49 
50 int main(){
51     while(scanf("%d %d",&n,&m)!=EOF){
52         if(n==0&&m==0) break;
53         
54         memset(g,0,sizeof(g));
55         memset(in,0,sizeof(in));
56         
57         while(m--){
58             int u,v;
59             cin>>u>>v;
60             g[u][v]=1;
61             in[v]++;
62         }
63         toposort();
64     }
65     return 0;        
66 }