拓扑序的主要应用就是检测图中是否有环。如果图中没有环，能生成一个拓扑序列，一般拓扑序列不唯一。
引入两个概念， “入度” 和 “出度”:
- 入度: 指向节点i的边有多少条
- 出度: 节点i指出去的边有多少条
拓扑排序的基本思路:
- 首先把入度为0的点加入到队列里面去
- 然后依次弹出队头，扩展对头后的指向的节点j如果入度为0，那么加入队列中去， 并删除该节点
- 如果加入的数据小于所有节点，说明有环，不存在拓扑序列。
- 如果等于节点个数，那么说明没有环，拓扑序列就是节点添加到队列的顺序
AcWing 848. 有向图的拓扑序列
来源: https://www.acwing.com/problem/content/850/
给定一个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$
输入样例：
输出样例：
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
| #include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], idx;
int q[N], hh, tt = -1;
int d[N];
int n, m;
int topsort()
{
for(int i = 1; i <= n; i++)
if (!d[i])
q[++tt] = i;
while(tt >= hh)
{
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (--d[j] == 0)
q[++tt] = j;
}
}
return tt >= n - 1;
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--)
{
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if (!topsort()) cout << -1 << endl;
else
{
for(int i = 0; i < n; i++)
printf("%d ", q[i]);
}
return 0;
}
|