POJ 3687 Labeling Balls（拓扑序列）

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

 

转载于:https://www.cnblogs.com/Silence-AC/p/3534723.html

总结

以上是生活随笔为你收集整理的POJ 3687 Labeling Balls（拓扑序列）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。