有向图的拓扑排序
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列
输入格式
- 第一行包含两个整数
n 和 m
- 接下来
m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x, y)
输出格式
- 共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可
- 否则输出
−1
数据范围
输入样例
输出样例
分析
- 邻接表的构建：
h[N]：存储每个节点的邻接表头e[N]：存储邻接节点的目标节点ne[N]：存储邻接表中链表的下一个节点idx：记录当前边的编号
add(a, b)：将一条从节点 a 到节点 b 的边加入邻接表topsort()：
- 使用队列
q 来存储入度为零的节点，初始化时将所有入度为零的节点加入队列
- 在
BFS 遍历过程中，若某个节点的入度减为零，则将其加入队列
- 最终，如果排序成功且队列中处理的节点数为
n，则说明拓扑排序存在，否则返回 false
时间复杂度
队列中的每个节点会被入队和出队一次，最多访问 n 个节点和 m 条边
时间复杂度 O(n + m)
空间复杂度
- 存储邻接表需要
O(n + m) 的空间
- 存储入度数组和队列需要
O(n) 的空间
空间复杂度为 O(n + m)
C++代码
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
61
62
63
64
65
66
67
|
#include <cstring>
#include <iostream>
const int N = 100010;
int h[N], e[N], ne[N], idx; // 邻接表
int q[N], d[N]; // 队列和入度数组
int n, m; // 节点数和边数
// 添加一条边到邻接表
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 拓扑排序算法
bool topsort()
{
int hh = 0, tt = -1;
// 将所有入度为 0 的节点加入队列
for (int i = 1; i <= n; ++i)
if (d[i] == 0)
q[++tt] = i;
// 进行拓扑排序
while (hh <= tt)
{
int t = q[hh++]; // 出队一个节点
for (int i = h[t]; i != -1; i = ne[i]) // 遍历该节点的所有邻接节点
{
int j = e[i]; // 邻接节点 j
if (--d[j] == 0) // 如果该节点的入度减为 0，则加入队列
q[++tt] = j;
}
}
// 如果队列中的节点数等于总节点数，说明拓扑排序成功
return tt == n - 1;
}
int main()
{
std::memset(h, -1, sizeof(h)); // 初始化邻接表
std::cin >> n >> m; // 输入节点数和边数
for (int i = 0; i < m; ++i)
{
int x, y;
std::cin >> x >> y; // 输入每条边
add(x, y); // 将边加入邻接表
++d[y]; // 更新节点 y 的入度
}
if (topsort()) // 如果拓扑排序成功
{
for (int i = 0; i < n; ++i) // 输出拓扑排序
std::cout << q[i] << ' ';
std::cout << '\n';
}
else
std::cout << -1 << '\n'; // 如果无法进行拓扑排序，输出 -1
return 0;
}
|
