POJ 3687 Labeling Balls（拓扑序列）

大意：n个重量分别为1-n的小球，给定一些小球间的重量关系。在符合重量关系的前提下，先输出编号小的球。

思路：也是一道很简单的拓扑排序，不过要倒着来，注意一下要判重边。

 1 #include <string.h>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 int Map[210][210], indegree[210], Ans[210];
 6 int n, m, x, y;
 7 int i, j;
 8 
 9 void Topo()
10 {
11     for(i = n; i >= 1; i--)
12     {
13         for(j = n; j >= 1; j--)
14         {
15             if(indegree[j] == 0)
16             {
17                 indegree[j]--;
18                 Ans[j] = i;
19                 for(int k = 1; k <= n; k++)
20                 {
21                     if(Map[j][k] == 1)
22                     {
23                         indegree[k]--;
24                     }
25                 }
26                 break;
27             }
28         }
29         if(j < 1)
30         {
31             break;
32         }
33     }
34     if(i >= 1)
35         cout << "-1" << endl;
36     else
37     {
38         for(i = 1; i <= n; i++)
39         {
40             if(i < n)
41             {
42                 cout << Ans[i] << " ";
43             }
44             else
45             {
46                 cout << Ans[i] << endl;
47             }
48         }
49     }
50 }
51 
52 void Solve()
53 {
54     int cases;
55     cin >> cases;
56     while(cases--)
57     {
58         memset(Map, 0, sizeof(Map));
59         memset(indegree, 0, sizeof(indegree));
60         cin >> n >> m;
61         for(i = 1; i <= m; i++)
62         {
63             cin >> x >> y;
64             if(!Map[y][x])
65             {
66                 Map[y][x] = 1;
67                 indegree[x]++;
68             }
69         }
70         Topo();
71     }
72 }
73 
74 int main()
75 {
76     Solve();
77 
78     return 0;
79 }

Labeling Balls