gogogo - 拓扑排序
type: channel
link: https://blog.folksaying.cn/index.php/category/topology/
description: 拓扑排序
items: 拓扑排序 R - Labeling Balls

拓扑排序 R - Labeling Balls
type: item
date: 2022-07-07T04:55:00+00:00
description: 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:No two balls share the same label.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?InputThe 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.OutputFor 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.SampleInputOutput54 0 4 1 1 1 4 2 1 2 2 1 4 1 2 1 4 1 3 21 2 3 4-1 -1 2 1 3 4 1 3 2 4翻译：Windy有N个不同重量的球，从1个单位到N个单位。现在，他试图用1到N来标记它们，这样：没有两个球共享相同的标签。标记满足几个约束，例如“标有 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。这题的思路就是用拓扑排序，拓扑排序一共有两种遍历方法，一种是从前往后，还有一种是从后往前，但从前往后遍历只能用来判断给定图是否是有向无环图，如果用来进行算法操作就会出问题，这题的正确解法如下：（如要细品前遍历和后便利的区别，可以试试样例这个样例）14 24 13 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--; // 将该标签的入度标记…