反向拓扑
介绍
反向拓扑是一个很常见的算法.解决的问题也很模板,是这样的一个问题:
有N个人，M个优先级a，b表示a优先于b。要求 ：编号最小的节点要尽量排在前面；在满足上一个条件的基础上，编号第二小的节点要尽量排在前面；在满足前两个条件的基础上，编号第三小的节点要尽量排在前面……依此类推。（注意，这和字典序是两回事，不能够混淆。
思路
这个思路初见还是真不好想.需要逆向思维.
6->1->3
5->2->4
以这两个为例,显然需要先令第一条链优先弹出.但是我们发现,在朴素的拓扑过程中,很难得到正确的结果,因为我们面对一条链的开始的时候,很难第一时间判断到底该选哪一个.
逆向思维.我们发现,各个链根据最后一个的元素的选择是确定的,因为前面的已经被弹走了,没有后顾之忧.也就是说,对于”让大的元素尽可能的向后放“是一个简单的贪心问题.我们只需要关注每个链的最后一个,然后选择他们之中最大的就可以.
事实上这样的方法正是解决之前问题的算法.
为了方便计算,我们反向建图,然后采取和字典序最小的算法类似的方法.求最大的字典序,得到的答案翻转过来,就是题目所要求的答案.
模板
HDU4857
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// #include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define maxn 30000+100
#define maxm 100000 + 10
#define ll long long
#define endl '\n'
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
struct {
int v, next;
} edge[2 * maxm];
int cnt;
int head[maxn];
int out[maxn];
int n, m;
void init(int rng) {
for (int i = 0; i <= rng; ++i) {
head[i] = -1;
}
cnt = 0;
}
void add(int u, int v) {
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void topo2() {
priority_queue<int, vector<int>, less<int>> q;
for (int i = 1; i <= n; ++i) {
if (!out[i]) {
q.push(i);
}
}
vector<int> ans;
while (!q.empty()) {
int cur = q.top();
ans.pb(cur);
q.pop();
for (int i = head[cur]; i + 1; i = edge[i].next) {
int v = edge[i].v;
if (!out[v])
continue;
--out[v];
if (!out[v]) {
q.push(v);
}
}
}
if (ans.size() < n) {
printf("-1\n");
} else {
for (int i = n - 1; i >= 0; --i) {
printf("%d%c", ans[i], i ? ' ' : '\n');
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
init(n);
for (int i = 0; i <= n; ++i) {
out[i] = 0;
}
for (int i = 0; i < m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add(v, u);
++out[u];
}
topo2();
}
return 0;
}
