[AcWing.848. 有向图的拓扑序列]

给定一个 n 个点 m 条边的有向图,点的编号是 1n,图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 -1

若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x, y)xA 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 nm

接下来 m 行,每行包含两个整数 xy,表示存在一条从点 x 到点 y 的有向边 (x, y)

输出格式

共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。

否则输出 -1

数据范围

1 < n,m < 10^5

输入样例:

1
2
3
4
3 3
1 2
2 3
1 3

输出样例:

1
1 2 3

算法思想

首先,存在拓扑序列,必定是有向无环图,如果是有向有环图一定没有拓扑序列,无向图更别说了。

核心思想

  1. n个节点,将入度为0的节点全部入队
  2. 删除掉所有入度为0的节点,在这个过程中,被删掉的节点不妨设为t
  3. 遍历t节点的邻边节点,让t节点的所有邻边节点入度减1,如果邻边节点入度被减之后恰好为0,则入队

此题,n的数量达到了10^5。所以需要使用邻接表,当然邻接矩阵算法也写下来,用于借鉴。
时间复杂度分别为o(n + m)o(n^2)

需要注意的是
邻接矩阵的重边造成的影响需要在加边的时候进行判断,维护入度,不让重边的出现导致入度混乱。

1
2
3
if(!g[a][b]){
// 加边
}

或者,在topsort的时候将重边一起删掉,也意味着重边入度也要减少
1
while(g[t][j]) --g[t][j],--d[j];

使用邻接表就不需要加判断了,因为邻接表在加边的时候,重边不仅加进去了,在topsort的时候
它会处理重边,所以入度一直是正确的。

代码实现1

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
68
69
70
71
72
73
#include <iostream>

using namespace std;

// 最大节点的数量
const int N = 100010;

// 节点数,边数
int n, m;

struct Node{
int id;
Node * next;
Node(int _id): id(_id), next(NULL){}
} * head[N]; // 邻接表

// 入度,队列
int d[N], q[N], hh = 0, tt = -1;

// 有向图头插法加边
void add(int a, int b){
// 创建b节点
Node * p = new Node(b);
// b节点的next指向原来节点a指向的next
p -> next = head[a];
// 节点a指向节点b
head[a] = p;
}

int topsort(){
// 将所有入度为0的节点加入队列之中
for(int i = 1; i <= n; i++)
if(!d[i])
q[++tt] = i;

// 删除掉所有入度为0的节点
while(hh <= tt){
int t = q[hh++];

// 遍历t节点的邻边节点
for(Node * p = head[t]; p; p = p -> next){
// 周边节点入度-1,如果入度为0,则加入队列
if(--d[p -> id] == 0){
q[++tt] = p -> id;
}
}
}
// n个节点都应该被删掉一次,那么tt达到 n - 1
return tt == n - 1;
}

int main(){

cin >> n >> m;

while(m --){
int a, b;
cin >> a >> b;
// a -> b
add(a, b);
d[b]++; // b的入度+1
}

// 如果图有环
if(!topsort()) puts("-1");
else{
// 合法拓扑序列恰好是 0 ~ tt,这里写成 < n也无妨,输出那n个节点(0 ~ n - 1)
for(int i = 0; i < n; i++)
cout << q[i] << " ";
}

return 0;
}

代码实现2

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
#include <iostream>

using namespace std;

const int N = 1010; // 假设最多有1000个顶点

int g[N][N]; // 邻接矩阵表示图
int d[N]; // 入度数组
int q[N], tt = -1, hh = 0; // 队列及其指针
// 节点数、边数
int n, m;

bool topsort() {
// 遍历所有节点,入度为0的点全部入队
for (int i = 1; i <= n; i++) {
if (!d[i]) {
q[++tt] = i;
}
}

// 装填完毕,删除当前节点,周边节点的入度-1,看是否为0,如果满足它们也入队
while (hh <= tt) {
int t = q[hh++];

for (int j = 1; j <= n; j++) {
if (g[t][j]) { // 如果存在边t->j
// 由于重边的影响,比如两次 2 -> 3
// 需要一口气将3的入度-2
while(g[t][j]) --g[t][j],--d[j];

if (d[j] == 0) {
q[++tt] = j;
}
}
}
}

return tt == n - 1;
}

int main() {

cin >> n >> m;

while (m--) {
int a, b;
cin >> a >> b;
g[a][b]++; // 边数+1
d[b]++; // b的入度+1
}

if (!topsort()) {
puts("-1");
} else {
for (int i = 0; i < n ; i++) {
cout << q[i] << " ";
}
cout << endl;
}

return 0;
}