拓扑排序 学习笔记

模板及讲解

用queue来存入度为0的点,然后BFS即可

常见题型

1、图中DP
Q: 给你一张图,你要在上面DP
解: 拓扑序保证无后效性,用拓扑序来DP转移
例题: Codeforces 919D
2、图中判环/无环
Q: 给你一张图,判图中有环/无环
解: 拓扑排序必须无环,如果没有拓扑某些点则有环
例题: Codeforces 915D

相关代码

hdu1285

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
vector<int> G[505];
int n, m, ino[505], ino2[505], tot;
bool topsort() {
queue<int> q;
for (int i = 1; i <= n; i++) if (ino2[i] == 0) tot++, q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
ino2[v]--;
if (ino2[v] == 0) tot++, q.push(v);
if (ino2[v] < 0) ino2[v] = 0;
}
}
if (tot == n) return 1; else return 0;
}
void clean() {
tot = 0, ms(ino, 0);
}
int solve() {
clean();
for (int u, v, i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v), ino[v]++;
}
for (int i = 1; i <= n; i++) {
memcpy(ino2, ino, sizeof ino);
if (!ino2[i]) continue;
ino2[i]--, tot = 0;
if (topsort()) return printf("YES\n"), 0;
}
printf("NO\n");
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
------ 本文结束 ------