AcWing0848 有向图的拓扑序列
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n ,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1 。
若一个由图中所有点构成的序列 A 满足:对于图中的每条边 ( x, y ) ,x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m 。
接下来 m 行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y 的有向边 ( x , y ) 。
输出格式
共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。
否则输出 −1 。
数据范围
1 ≤ n , m ≤ 10^5
输入样例:
3 3
1 2
2 3
1 3
输出样例:
1 2 3
算法思想1-Kahn算法:
用一个队列 queue<int> que
维护当前所有入度为 0 的点。排序过程如下:
- 初始化。遍历所有节点,将各入度为 0 的节点压入队列。
- 队头出队,并删除所有从该节点出发的有向边。如果边删除后边指向的顶点的入度减为 0 ,则将其入队。
- 循环执行步骤 2 ,直至队列为空。若所有节点已排序,则该序列为一个可能的拓扑序列。否则,说明拓扑序列不存在。
算法1-Kahn算法:
#include <iostream>
#include <queue>
using namespace std;
const int N = 100000, M = 100000;
int n, idx;
int first[N + 1], ne[M + 1], vertex[M + 1];
int sorted[N + 1], indegree[N + 1];
void addEdge(int a, int b) {
vertex[++idx] = b; // 创建新边 idx
ne[idx] = first[a]; // 头插法
first[a] = idx;
++indegree[b];
}
bool topoSort() {
// 初始化队列:将所有入度为 0 的顶点入队
queue<int> que;
for (int i = 1; i <= n; ++i) {
if (!indegree[i]) {
que.push(i);
}
}
int cnt = 0;
while (que.size()) {
// 队头出队并排序
int u = que.front();
que.pop();
sorted[++cnt] = u;
// 遍历并删除 u 的所有出边
for (int i = first[u]; i; i = ne[i]) {
int v = vertex[i];
if (--indegree[v] == 0) {
que.push(v);
}
}
}
// 若所有点已排序,返回 true ,否则返回 false
return cnt == n ? true : false;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int m;
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
addEdge(a, b);
}
if (topoSort()) {
for (int i = 1; i <= n; ++i) {
cout << sorted[i] << " ";
}
}
else {
cout << "-1";
}
return 0;
}