拓扑排序

前置知识

DAG，是有向图（有向无环图）的简称。

拓扑排序的定义

如果 DAG 的一个遍历序列满足：

1. 每个点都访问了一遍。
2. 对于每个便，出发节点在目的地节点的前面输出。

求拓扑排序

定义 $d_i$ 为第 $i$ 个节点的入度。

用邻接表储存一个正向建边和反向建边。

如果某个节点的入度为 $0$，那么输出这个节点，并且加入队列。

遍历队列的每个元素，给每个元素的入度减一，并且检查 $d_i$ 是否为 $0$，如果减完后入度为 $0$，那么输出，并加入队列。

重复上面的操作，直到队列为空。

我们会发现拓扑排序已经求出来了。

例题

B3644 【模板】拓扑排序 / 家谱树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n;
vector <int> v[100005], v2[100005];
int d[100005];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int x;
        while (cin >> x) {
            if (x == 0) break;
            else v[x].push_back(i), d[x] ++, v2[i].push_back(x);
        }
    } 
    queue <int> q;
    for (int i = 1; i <= n; i ++) {
        if (v[i].size() == 0) {
            cout << i << " ";
            q.push(i);
        }
    }
    // cout << "*\n" << v2[q.front()].size();
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < v2[x].size(); i ++) {
            d[v2[x][i]] --;
            // cout << d[v[x][i]] << " ";
            if (d[v2[x][i]] == 0) {
                cout << v2[x][i] << " ";
                q.push(v2[x][i]);
            } 
        }
    }
    return 0;
}