拓扑排序

拓扑排序

Kahn算法 洛谷P3386

cpp
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
#include <bits/stdc++.h>

struct Edge {
int v;
};
using AdjList = std::vector<std::vector<Edge>>;

std::vector<int> toposort(const AdjList& G) {
const int N = G.size();
std::vector<int> indeg(N);
for (int u = 0; u < N; ++u)
for (auto&& e : G[u]) ++indeg[e.v];
std::vector<int> ord;
ord.reserve(N);
std::queue<int> q;
for (int u = 0; u < N; ++u)
if (!indeg[u]) q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
ord.push_back(u);
for (auto&& e : G[u])
if (!--indeg[e.v]) q.push(e.v);
}
return ord;
}

using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
AdjList G(N);
for (int u = 0, v; u < N; ++u)
while (cin >> v, v) G[u].emplace_back(Edge{v - 1});
auto topo = toposort(G);
for (int u : topo) cout << u + 1 << ' ';
return 0;
}

拓扑排序
https://blog.fredbill.eu.org/2023/12/25/算法/图论/拓扑排序/
作者
FredBill
发布于
2023年12月25日
许可协议