#创作计划#拓扑排序（未完）
2026-04-07 18:26:23
发布于：上海
拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序．
OI-wiki
前置芝士： BFS 邻接表
定义：
有向无环图 ()：
顾名思义，该图边有向且无环。
其性质为能拓扑排序的图和 是成对应关系的。
即一 必然能进行拓扑排序，反之亦然。
拓扑排序，是指将图中的顶点以线性方式进行排序，使得对于任何的顶点 到 的有向边 , 都可以有 在 的前面．
一个 的拓扑序不一定唯一。
例：
对于该图，可能的拓扑序为 , 等。
构造拓扑序列步骤
从图中选择一个入度为 的点。
记录该顶点，从图中删除此顶点及其所有的出边，统计入度。
重复上面两步，直到所有顶点都被记录，拓扑排序完成。
若图中不存在入度为零的点但仍有点未被记录，此时说明图是有环图，拓扑排序无法完成。
实现：
一般采用
初始状态下，集合 装着所有入度为 的点， 是一个空列表。
每次从 中取出一个点 （可以随便取）放入 , 然后将 的所有边 删除。
对于边 ，若将该边删除后点 的入度变为 ，则将 放入 中．
不断重复以上过程，直到集合 为空．检查图中是否存在任何边，如果有，那么这个图一定有环。
否则 中顶点的顺序就是构造拓扑序列的结果．
模板：
#include <bits/stdc++.h>
using namespace std;
#define N 100005
vector <int> g[N]; // 存图
int in[N]; // 记录入度
int main() {
int n, m; // 点数 & 边数
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y; // 每一条边
cin >> x >> y;
g[x].push_back(y); //存边
in[y]++; // 记录入度
}
queue <int> q;
// 字典序最大：priority_queue <int> q; (默认为大根堆)
// 字典序最小：priority_queue <int, vector <int>, greater <int> > q;
// 注意使用 pq 要用 q.top() 而非 q.front()
vector <int> ans;
for (int i = 1; i <= n; i++) if (in[i] == 0) q.push(i); // 初始化
while (!q.empty()) {
int t = q.front();
q.pop();
ans.push_back(t); // 记录
for (int i : g[t]) {
in[i]--; // 删边（减入度）
if (in[i] == 0) q.push(i); // 判断，是加入集合
}
}
return 0;
}
此时若 存储了所有节点，则原图为有向无环图。
否则原图有环。
此实现方式 时间复杂度 ，若使用优先队列，时间复杂度变为 。
例题
A29810
大意：
给定一图，若其为 输出拓扑序列，反之输出 has circle.
一道板子，注意输出格式。
#include <bits/stdc++.h>
using namespace std;
#define N 55
vector <int> g[N]; // 存图
int in[N]; // 记录入度
int main() {
int n, m; // 点数 & 边数
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y; // 每一条边
cin >> x >> y;
g[x].push_back(y); //存边
in[y]++; // 记录入度
}
priority_queue <int, vector <int>, greater <int> > q;
vector <int> ans;
for (int i = 1; i <= n; i++) if (in[i] == 0) q.push(i); // 初始化
while (!q.empty()) {
int t = q.top();
q.pop();
ans.push_back(t); // 记录
for (int i : g[t]) {
in[i]--; // 删边（减入度）
if (in[i] == 0) q.push(i); // 判断，是加入集合
}
} if (ans.size() == n) for (int i : ans) cout << i << " ";
else cout << "has circle.";
return 0;
}
拓扑排序亦可以和 DP 结合。
例题：
A85523
大意：给定一图，对于一边 动物 可以吃掉动物 。
求最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者这样的链的总数，对 取模。
思路：
因为要一端是生产者，故要记录出度。
同时，若对于一点 能直接连接到 则进行累加，将每一点在拓扑排序时增加所有上级的即可。
最后统计出度为零的点的方案总数。
#include <bits/stdc++.h>
using namespace std;
const int MOD = 80112002;
vector <int> g[5005];
int in[5005], out[5005], dp[5005];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
in[y]++;
out[x]++;
}
queue <int> q;
vector <int> ans;
for (int i = 1; i <= n; i++) if (in[i] == 0) q.push(i), dp[i] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
ans.push_back(t);
for (int i : g[t]) {
dp[i] += dp[t];
dp[i] %= MOD;
if (--in[i] == 0) q.push(i);
}
} int sum = 0;
for (int i = 1; i <= n; i++) if (out[i] == 0) sum += dp[i], sum %= MOD;
cout << sum;
return 0;
}
例题：
A226
大意：
有 个点，每个点有一个点权。
有 个序列，并且满足要求：若包含点 ，则序列内所有点的点权都大于等于 的点权。
求最大点权的最小值。
思路：
考虑序列中的相邻点 和 ：
它们之间的站点 都是未停靠的。
对于中间任一未停靠站
的点权必然小于 ，否则 必须加入序列。
随后在拓扑时记录答案数组即可。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
int mp[maxn][maxn], deg[maxn], a[maxn], step[maxn];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
int vis[maxn] = {0};
for (int j = 1; j <= x; j++) {
cin >> a[j];
vis[a[j]] = 1;
} for (int j = 1; j <= x; j++) {
for (int k = a[1]; k <= a[x]; k++) {
if (vis[k] || mp[k][a[j]]) continue;
mp[k][a[j]] = 1;
deg[a[j]]++;
}
}
} queue <int> q;
for (int i = 1; i <= n; i++) if (deg[i] == 0) {
q.push(i);
step[i] = 1;
} while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
int v = i;
if (!mp[u][v]) continue;
step[v] = max(step[v], step[u] + 1);
deg[v]--;
if (deg[v] == 0) q.push(v);
}
} cout << *max_element(step + 1, step + n + 1);
return 0;
}
P1113
有 n 个任务，编号 。
每个任务都有完成所需的时间。
任务之间有依赖关系：某些任务必须先于另一些任务完成。
可以同时做任意个任务。
求所有任务完成的最短时间。
思路：
等一下写（
#include <bits/stdc++.h>
using namespace std;
pair <int, vector <int> > g[10005];
int in[10005], dp[10005];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int len, k;
cin >> len >> k;
g[i].first = len;
for (int j = 1; j <= k; j++) {
int x;
cin >> x;
in[i]++;
g[x].second.push_back(i);
}
} queue <int> q;
for (int i = 1; i <= n; i++) if (in[i] == 0) {
q.push(i);
dp[i] = g[i].first;
} while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u].second) {
dp[v] = max(dp[v], dp[u] + g[v].first);
if (--in[v] == 0) q.push(v);
}
} cout << *max_element(dp + 1, dp + n + 1);
return 0;
}
全部评论 7
- 置顶
主播如果缺题了给你亿点：洛谷P1113、1347、1685、3243、1983、1083、4934、4017、2597，poj1094、2367、2585、1128，hdu 1285、3342、2647、4857、1811
2026-04-06 来自 上海
0
有帮助，赞一个