POJ 3687 Labeling Balls 逆向建图，拓扑排序

要逆向建图，输入的时候要判重边，找入度为0的点的时候要从大到小循环，尽量让编号大的先入栈，输出的时候注意按编号的顺序输出重量，不是按重量大小输出编号。。

题目确实很简单，但是感觉很经典。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stack>
 4 using namespace std;
 5 bool graph[210][210], vis[210];
 6 int n, m, indegree[210], weight[210];
 7 stack<int>s;
 8 
 9 bool toposort()
10 {
11     while(!s.empty())s.pop();
12     memset(vis, 0, sizeof(vis));
13     int cnt = 0;
14     for(int i = 0; i < n; i++)
15     {
16         for(int j = n; j >= 1; j--)
17         {
18             if(indegree[j] == 0 && !vis[j])
19             {
20                 cnt++;
21                 s.push(j);
22                 vis[j] = 1;
23                 for(int k = 1; k <= n; k++)
24                 {
25                     if(graph[j][k])
26                         indegree[k]--;
27                 }
28                 break;
29             }
30         }
31     }
32     return cnt == n;
33 }
34 
35 void solve()
36 {
37     int w = 1;
38     while(!s.empty())
39     {
40         int u = s.top();
41         s.pop();
42         weight[u] = w++;
43     }
44     for(int i = 1; i < n; i++)
45         printf("%d ", weight[i]);
46     printf("%d
", weight[n]);
47 }
48 
49 int main()
50 {
51     int t, u, v;
52     scanf("%d", &t);
53     while(t--)
54     {
55         scanf("%d %d", &n, &m);
56         memset(graph, 0, sizeof(graph));
57         memset(indegree, 0, sizeof(indegree));
58         for(int i = 0; i < m; i++)
59         {
60             scanf("%d %d", &u, &v);
61             if(!graph[v][u])
62             {
63                 graph[v][u] = 1;
64                 indegree[u]++;
65             }
66         }
67         if(toposort())
68             solve();
69         else printf("-1
");
70     }
71     return 0;
72 }

View Code