题解 | #【模板】拓扑排序#

初学图，配合章老师的【7.8 拓扑排序之算法实现】https://www.bilibili.com/video/BV1Qb4y1h7HY?vd_source=a6f22bf63a765351b788dbc276780f95视频完成练习

#include <bits/stdc++.h>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    // 入度容器
    vector<int> in(n + 1, 0);
    // 有向无环图邻接表
    vector<vector<int>> out(n + 1);
    // 初始化图
    while (m--) {
        int from, to;
        cin >> from >> to;
        out[from].push_back(to);
        in[to]++;
    }
    // 初始化栈
    stack<int> wait;
    queue<int> res;
    // 遍历邻接表的入度 (因为结点值（入度容器下标）大于等于1，所以从1开始循环)
    for (int v = 1; v < in.size() ; v++) {
        if (in[v] == 0) wait.push(v);
    }
    // 拓扑排序
    while (!wait.empty()) {
        // 删除图中下标序，最后一个结点，并存入结果中
        int val = wait.top();
        wait.pop();
        res.push(val);
        // 删除该结点的边，调整入度容器
        for (auto nodeVal : out[val]) {
            in[nodeVal]--;
            // 将调整后，入度为0的结点存入栈中
            if (in[nodeVal] == 0) wait.push(nodeVal);
        }
    }
    // 有向无环图（DAG）排序后长度为节点个数
    if (res.size() == n){
        // 遍历结果
        for (int i = 0 ; i < n ; i++){
            cout << res.front();
            res.pop();
            if (i != n - 1) cout << ' ';
        }
    } else {
        cout << -1;
    }
}