拓扑排序算法c++

拓扑排序是一种基于有向无环图(DAG)的排序算法，它将图中的节点按照其依赖关系排序，使得每个节点都排在它的后继节点之前。

下面是一份C++代码实现：

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

const int N = 10010;

int n, m;
int in_degree[N];  // 记录每个节点的入度
vector<int> G[N];  // 记录每个节点的后继节点

// 拓扑排序
bool topological_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        in_degree[v]++;
    }
    if (topological_sort()) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

该算法的时间复杂度为$O(n+m)$，其中$n$是节点数，$m$是边数。