hdu 1285 确定比赛名次 拓扑排序

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #define inf 0x7fffffff
 9 using namespace std;
10 const int maxn=500+10;
11 
12 int n,m;
13 struct node
14 {
15     int u;
16     friend bool operator < (node a,node b)
17     {
18         return a.u > b.u;
19     }
20 }cur,tail;
21 int graph[maxn][maxn],in[maxn];
22 int an[maxn],cnt;
23 
24 void topsort()
25 {
26     cnt=0;
27     priority_queue<node> Q;
28     for (int i=1 ;i<=n ;i++) if (in[i]==0)
29     {
30         cur.u=i;
31         Q.push(cur);
32     }
33     while (!Q.empty())
34     {
35         cur=Q.top() ;Q.pop() ;
36         int u=cur.u;
37         an[cnt++]=u;
38         for (int i=1 ;i<=n ;i++)
39         {
40             if (graph[u][i] && i!=u)
41             {
42                 in[i]--;
43                 if (in[i]==0)
44                 {
45                     cur.u=i;
46                     Q.push(cur);
47                 }
48             }
49         }
50     }
51     int flag=0;
52     for (int i=0 ;i<cnt ;i++)
53     {
54         if (flag) printf(" ");
55         flag=1;
56         printf("%d",an[i]);
57     }
58     printf("\n");
59 }
60 
61 int main()
62 {
63     while (scanf("%d%d",&n,&m)!=EOF)
64     {
65         int a,b;
66         memset(graph,0,sizeof(graph));
67         memset(in,0,sizeof(in));
68         for (int i=1 ;i<=m ;i++)
69         {
70             scanf("%d%d",&a,&b);
71             if (graph[a][b]==0) in[b] ++ ;
72             graph[a][b]=1;
73         }
74         topsort();
75     }
76     return 0;
77 }