拓扑排序 C++

拓扑排序是一种经典的算法，用于对有向无环图（DAG）进行排序。它的思想是对DAG进行排序，使得每个顶点的前驱节点排在它的后面。以下是使用C++实现拓扑排序的示例代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> topo_sort(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> in_degree(n, 0);
    for (auto& v : graph) {
        for (int u : v) {
            in_degree[u]++;
        }
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }
    vector<int> res;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        for (int v : graph[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    return res;
}

int main() {
    // 构建图
    vector<vector<int>> graph = {{1, 2}, {3}, {3}, {4, 5}, {5}, {}};
    // 拓扑排序
    vector<int> res = topo_sort(graph);
    // 输出结果
    for (int u : res) {
        cout << u << " ";
    }
    cout << endl;
    return 0;
}

在上述示例代码中，我们首先统计每个顶点的入度，然后将入度为0的顶点放入队列中，从队列中取出一个顶点时，将该顶点加入结果中，并将该顶点的后继节点的入度减1，如果减1后入度为0，则将该后继节点加入队列中。最终返回结果即为拓扑排序的结果。