www.luogu.com.cn

拓扑排序

定义与实现思路

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

  1. 每个顶点出现且只出现一次。

  2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

根据定义可知，我们可以使用队列+BFS的方式求出一个图的拓扑序列，方法如下：

  1. 存图的时候记录下每个点的前驱数（即入度）。

  2. 从图中选择一个 没有前驱（即入度为 00）的顶点并输出，将其加入队列当中。

  3. 重复步骤 22 直到队列中的元素个数为 00 时，停止程序。

tips\bold tips：通常，一个有向无环图可以有一个或多个拓扑排序序列。

代码实现

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
// Problem: B3644 【模板】拓扑排序 / 家谱树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3644
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e3 + 9;
const int INF = 0x3f3f3f3f;
vector<int> g[N];
int n, x, in[N];
queue<int> q;

int main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        while (cin >> x && x != 0)
        {
            g[i].push_back(x);
            in[x]++;
        }
    for (int i = 1; i <= n; i++)
        if (in[i] == 0)
        {
            cout << i << ' ';
            q.push(i);
        }
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (auto i : g[x])
        {
            in[i]--;
            if (in[i] == 0) {
                cout << i << ' ';
                q.push(i);
            }
        }
    }
    return 0;
}