拓扑排序

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100010;

vector<int> adj[N];  // 邻接表：adj[u] 存 u 指向的所有节点
int in[N];            // in[i] = 节点 i 的入度

// 拓扑排序：返回排序结果，如果结果长度 < n 说明有环
vector<int> topoSort(int n) {
    queue<int> q;  // 存放入度为0的节点

    // 第1步：找到所有入度为0的节点，入队
    for (int i = 1; i <= n; i++) {  // 注意：节点编号从1开始
        if (in[i] == 0) {
            q.push(i);  // 没有前置依赖，可以最先执行
        }
    }

    vector<int> order;  // 存放拓扑排序结果

    // 第2步：BFS 过程
    while (!q.empty()) {
        int u = q.front();  // 取出一个入度为0的节点
        q.pop();
        order.push_back(u);  // 加入结果序列

        // 把 u "去掉"后，它指向的所有节点入度-1
        for (int v : adj[u]) {
            in[v]--;       // u 被处理了，v 的一个前置完成了
            if (in[v] == 0) {
                q.push(v);  // v 的所有前置都完成了，可以执行了
            }
        }
    }

    return order;  // 如果 order.size() < n，说明图中有环
}

int main() {
    int n, m;  // n 个节点，m 条边
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;  // u → v 表示 u 是 v 的前置
        adj[u].push_back(v);  // u 指向 v
        in[v]++;              // v 的入度+1
    }

    vector<int> result = topoSort(n);

    if (result.size() < n) {
        cout << "图中有环，无法拓扑排序！" << endl;
    } else {
        for (int x : result)
            cout << x << " ";
        cout << endl;
    }
    return 0;
}