图论

拓扑排序

拓扑排序的定义

拓扑排序：在一个 $DAG$（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$, $u$ 都在 $v$ 的前面。

形式化地，设 $q_i$ 表示结点 $i$ 在 $p$ 中的位置，那么对于图上每条有向边 $u \rightarrow v$ ，均有 $q_u < q_v$ 。

拓扑排序的实现

由于原图无环，所以在拓扑排序没有结束的时候必然存在入度为 $0$ 的节点，将这个点加入 $p$ 并删去其出边。

可以通过 $BFS$ 或者 $DFS$ 实现，时间复杂度为 $O(N + M)$ 

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
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector<int>> e(n + 1);
	vector<int> in(n + 1);
	auto add = [&](int u, int v) {
		in[v]++;
		e[u].push_back(v);
		e[v].push_back(u);
	};
	for(int u = 1; u <= n; u++) {
		int v;
		cin >> v;
		while(v) {
			add(u, v);
			cin >> v;
		}
	}
	queue<int> q;
	vector<int> p;
	for(int u = 1; u <= n; u++) {
		if(!in[u]){
			p.push_back(u);
			q.push(u);
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(auto v : e[u]) {
			in[v]--;
			if(!in[v]) {
				q.push(v);
				p.push_back(v);
			}
		}
	}
	for(auto x : p) {
		cout << x << ' ';
	}
	return 0;
}

拓扑序的性质

有向图有环的充要条件是无拓扑序。

$DAG$ 拓扑序不唯一， $DAG$ 的拓扑序计数问题无多项式时间复杂度的算法，但是树形图的拓扑序计数存在多项式时间复杂度的算法。

拓扑排序的拓展与应用

可以将 $DAG$ 中的有向边抽象成偏序关系，可以通过拓扑排序判断元素集是否满足偏序关系。

例题

[ABC277F] Sorting a Matrix

首先行列之间的操作是互不影响的，所以我们可以将问题转化成先进行列交换再进行行交换。

求最大（最小）字典序拓扑序在 BFS 求拓扑序时，将队列换成优先队列。

例题

P3243 [HNOI2015] 菜肴制作

我们可以贪心令最后一位数字 $X$ 尽可能的大。假设最优解的最后一位数字是 $Y (Y < X)$，显然 $V_X$ 不存在出边，所以最优的变化相当于$X$ 与 $Y$的交换，所以这个方案相对于前者不能满足先选到 $Y$ 。于是答案是翻转反图字典序最大的拓扑序。

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
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> e(n + 1);
	vector<int> in(n + 1, 0);
	int cnt = 0;
	auto add = [&] (int u, int v) {
		e[u].push_back(v);
		in[v]++;
	};
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		add(v, u);
	}
	stack<int> ans;
	priority_queue<int> q;
	for(int u = 1; u <= n; u++) {
		if(!in[u]) {
			q.push(u);
		}
	}
	while(!q.empty()) {
		int u = q.top();
		q.pop();
		ans.push(u);
		for(auto v : e[u]) {
			in[v]--;
			if(!in[v]) {
				q.push(v);
			}
		}
	}
	if(ans.size() < n) {
		cout << "IMPOSSIBLE" << endl;
	}
	else {
		while(!ans.empty()) {
			int x = ans.top();
			cout << x << ' ';
			ans.pop();
		}
		cout << endl;
	}
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

例题

CF1765H Hospital Queue

首先一个合法的构造方案是尽量让 $p_i$ 大的靠后，这个可以建反图跑（最大字典序）拓扑排序实现，然后我们可以枚举第 $k$ 个病人的位置， 判断是否可行。然后我们发现是否可行具有单调性，所以可以二分答案，时间复杂度 $O((m + n) * \log^2n)$ 。据说会 $TLE$ 。我们可以充分发挥一下人类智慧，如果想让第 $k$ 个病人的位置尽可能靠前，我们只需要让其他病人的位置尽可能靠后就行了，空出来的位置就是病人 $k$ 的位置，我们只需要在拓扑排序的时候先忽略第 $k$ 个病人，从后往前加到不加 $k$ 则不符合 $p_i$ 的约束的，或者除了必须在 $k$ 前面的病人以外都加上了的位置就是答案，时间复杂度 $O((m + n) * \log n)$。 

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
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int check(vector<vector<int>> e, vector<int> in, vector<int> id, int p) {
	int n = e.size() - 1;
	stack<int> ans;
	priority_queue<pair<int, int>> q;
	for(int u = 1; u <= n; u++) {
		if(!in[u] && u != p) {
			q.push(make_pair(id[u], u));
		}
	}
	while(!q.empty() && q.top().first >= n - ans.size()) {
		int u = q.top().second;
		q.pop();
		ans.push(u);
		for(auto v : e[u]) {
			in[v]--;
			if(!in[v] && v != p) {
				q.push(make_pair(id[v], v));
			}
		}
	}
	return n - ans.size();
}
void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> e(n + 1);
	vector<int> in(n + 1, 0), id(n + 1);
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		cin >> id[i];
	}
	auto add = [&] (int v, int u) {
		e[u].push_back(v);
		in[v]++;
	};
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	for(int i = 1; i <= n; i++) {
		cout << check(e, in, id, i) << ' ';
	}
}

int main() {
	int t = 1;
	while(t--) {
		solve();
	}
	return 0;
}

参考资料

图论基础 alex-wei

拓扑排序 oi-wiki

拓扑序 未欣

拓扑学习笔记 whiteqwq