[POJ] 3687 Labeling Balls(拓扑排序)

反向建边，即重的球指向轻的球，注意重边，然后拓扑排序。从n-->1循环，即每次从入度为0的球里面选编号大的存(包含输入的逻辑关系中没出现的球)。最后不成立输出-1，否则正向输出编号。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<stdbool.h>
 7 #include<time.h>
 8 #include<stdlib.h>
 9 #include<set>
10 #include<map>
11 #include<stack>
12 #include<queue>
13 #include<vector>
14 using namespace std;
15 #define clr(x,y)    memset(x,y,sizeof(x))
16 #define sqr(x)      ((x)*(x))
17 #define rep(i,a,b)  for(int i=(a);i<=(b);i++)
18 #define LL          long long
19 #define INF         0x3f3f3f3f
20 #define A           first
21 #define B           second
22 const int N=200+11;
23 int     n,m,cnt,head[N],d[N],path[N];
24 bool    f[N][N];
25 
26 struct node
27 {
28     int v,u;
29     int next;
30 } edge[N*N];
31 
32 void init()
33 {
34     clr(d,0);
35     clr(f,0);
36     clr(head,-1);
37     clr(path,0);
38     cnt=0;
39 }
40 
41 void add(int u,int v)
42 {
43     edge[cnt].v=v;
44     edge[cnt].next=head[u];
45     head[u]=cnt++;
46 }
47 
48 bool toposort(int n)
49 {
50     int flag=0;
51     
52     for(int i=n;i>=1;i--){
53         flag=1;
54         for(int j=n;j>=1;j--) {
55             if(!d[j]) {
56                 flag=0;
57                 path[j]=i;
58                 d[j]--;
59                 for(int k=head[j];k!=-1;k=edge[k].next) {
60                     d[edge[k].v]--;
61                 }
62                 break;
63             }
64         }
65         if(flag) break;
66     }
67     return flag;
68 }
69 
70 int main()
71 {
72     int cas,x,y;
73     
74     scanf("%d",&cas);
75     while(cas--) {
76         init();
77         scanf("%d%d",&n,&m);
78         while(m--) {
79             scanf("%d%d",&x,&y);
80             if(!f[y][x]) {
81                 f[y][x]=1;
82                 add(y,x);
83                 d[x]++;
84             }
85         }
86         int flag=toposort(n);
87         if(!flag){
88             for(int i=1;i<=n;i++) {
89                 printf("%d%c",path[i],i==n?'
':' ');
90             }
91         } else {
92             puts("-1");
93         }
94         
95     }
96     
97     return 0;
98 }