Labeling Balls(拓扑)

看题意看了半天没看懂怎么回事，看完Discuss彻底凌乱了。。后来看了题解才懂，就是逆向建图+拓扑排序，建图时要判重边。

 1 #include<stdio.h>
 2 #include<string.h>
 3 int map[202][202];
 4 int n,in[202],ans[202];
 5 int topo()
 6 {
 7     int i,j;
 8     for (i = n; i >= 1; i --)
 9     {
10         for (j = n; j >= 1; j --)
11         {
12             if (!in[j])
13             {
14                 ans[j] = i;
15                 --in[j];
16                 break;
17             }
18         }
19         if (j < 1) return 0;
20         for  (int k = 1; k <= n; k ++)
21         {
22             if (map[j][k])
23                 --in[k];
24         }
25     }
26     return 1;
27 }
28 int main()
29 {
30     int m,t,a,b;
31     scanf("%d",&t);
32     while(t--)
33     {
34         scanf("%d%d",&n,&m);
35         memset(map,0,sizeof(map));
36         memset(ans,0,sizeof(ans));
37         memset(in,0,sizeof(in));
38         for (int i = 1; i <= m; i ++)
39         {
40             scanf("%d%d",&a,&b);
41             if (!map[b][a])
42             {
43                 map[b][a] = 1;
44                 ++in[a];
45             }
46         }
47         if (topo())
48         {
49             for (int i = 1; i <= n; i ++)
50             {
51                 if (i==1)
52                     printf("%d",ans[i]);
53                 else
54                     printf(" %d",ans[i]);
55             }
56             puts("");
57         }
58         else
59             puts("-1");
60     }
61     return 0;
62 
63 }

View Code