Loading... > **Windy has ***N* balls of distinct weights from 1 unit to *N* units. Now he tries to label them with 1 to *N* in such a way that: 1. **No two balls share the same label.** 2. **The labeling satisfies several constrains like "The ball labeled with ***a* is lighter than the one labeled with *b".* > **Can you help windy to find a solution?** **Input** > **The first line of input is the number of test case. The first line of each test case contains two integers, ***N* (1 ≤ *N* ≤ 200) and *M* (0 ≤ *M* ≤ 40,000). The next *M* line each contain two integers *a* and *b* indicating the ball labeled with *a* must be lighter than the one labeled with *b*. (1 ≤ *a, b* ≤ *N*) There is a blank line before each test case. **Output** > **For each test case output on a single line the balls' weights from label 1 to label ***N*. If several solutions exist, you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... If no solution exists, output -1 instead. **Sample** | **Input** | **Output** | | ---------------------------------------------------------------------------------- | -------------------------------------------------- | | 5<br>4 0 <br>4 1<br> 1 1<br> 4 2 <br>1 2<br> 2 1<br> 4 1<br> 2 1<br> 4 1<br> 3 2 | 1 2 3 4<br />-1 <br>-1 <br />2 1 3 4 <br>1 3 2 4 | **翻译：** > **Windy有***N*个不同重量的球，从1个单位到*N个*单位。现在，他试图用1到*N*来标记它们，这样： 1. **没有两个球共享相同的标签。** 2. **标记满足几个约束，例如“标有 ***a* 的球比标有 b 的球轻*”。* > **你能帮助Windy找到解决方案吗？** **输入** > **输入的第一行是测试用例的数量。每个测试用例的第一行包含两个整数，***N*（1 ≤ *N* ≤ 200）和 *M*（0 ≤ *M* ≤ 40，000）。下一行 *M* 行各包含两*个整数 a* 和 *b*，表示标有 *a* 的球必须比标有 *b* 的球轻。（1 ≤ *a， b* ≤ *N*）每个测试用例之前都有一个空行。 **输出** > **对于单行上的每个测试用例输出，球的权重从标签 1 到标签 ***N*。如果存在多个解决方案，则应输出标签 1 的权重最小的解决方案，然后输出标签 2 的最小权重的解决方案，然后输出标签 3 的最小权重的解决方案，依此类推...如果不存在解决方案，请改为输出 -1。 **这题的思路就是用拓扑排序，拓扑排序一共有两种遍历方法，一种是从前往后，还有一种是从后往前，但从前往后遍历只能用来判断给定图是否是有向无环图，如果用来进行算法操作就会出问题，这题的正确解法如下：（如要细品前遍历和后便利的区别，可以试试样例这个样例）** > **1** > > **4 2** > > **4 1** > > **3 2** ``` # include<iostream> # include<cstring> using namespace std; const int N=310; int cnt[N],ans[N]; bool vis[N], mp[N][N]; int n,m; bool topological_sort() { // 从后往前遍历 int weight=n; // 有n个标签，故循环n次 for(int i = 1; i <= n; ++ i) { int now=0; // 从后往前遍历，寻找入度为零的标签 for(int j = n; j >= 1; -- j) { if(!vis[j] && cnt[j]==0) { now=j; break; } } // 如果找不到了就退出循环 if(!now) break; // 标记该标签已访问 vis[now]=true; // 记录该标签当前的重量 ans[now]=weight--; // 将该标签的入度标记为-1，表示该标签不能再被使用了 cnt[now]=-1; for(int j = 1; j <= n; j++) { // 将所有比now重的入度减一 if(!vis[j] && mp[j][now]) { -- cnt[j]; } } } return weight==0; } void init() { memset(vis, false, sizeof vis); memset(cnt, 0, sizeof cnt); memset(mp, 0, sizeof mp); } /* 从前往后遍历，每次取最轻的，由轻指向重的，记录重的为入度（bu 从后往前遍历，每次取最重的，由重指向轻的，记录轻的为入度 */ int main() { int t; scanf("%d", &t); while(t--) { // 初始化 init(); // 输入数据 scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++) { int x,y; scanf("%d %d", &x, &y); // 记录节点入度 if(!mp[x][y]) { mp[x][y] = true; // 记录轻的为入度 ++ cnt[x]; } } // 如果找到解决方案输出true，否则输出false if(topological_sort()) { for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; } else cout<<"-1"<<endl; } } ``` **参考博客** [poj3687~拓扑排序（附上拓扑排序详解）](http://t.csdn.cn/nNxdV) 最后修改：2022 年 07 月 07 日 © 允许规范转载 赞 1 如果觉得我的文章对你有用，请随意赞赏
