拓扑排序算法的实现c++

以下是一个用C++实现的拓扑排序算法的例子：

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

vector<int> topologicalSort(int n, vector<vector<int>>& graph) {
    vector<int> indegree(n, 0);
    vector<int> result;
    queue<int> q;

    // 计算每个顶点的入度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            int v = graph[i][j];
            indegree[v]++;
        }
    }

    // 将入度为0的顶点加入队列
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
            result.push_back(i);
        }
    }

    // 拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            indegree[v]--;

            if (indegree[v] == 0) {
                q.push(v);
                result.push_back(v);
            }
        }
    }

    // 如果输出的顶点数小于有向图的顶点数，则说明有回路
    if (result.size() < n) {
        result.clear();
    }

    return result;
}

int main() {
    int n = 6; // 顶点数
    vector<vector<int>> graph(n);

    // 添加有向边
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[3].push_back(5);
    graph[4].push_back(5);

    vector<int> result = topologicalSort(n, graph);

    if (result.empty()) {
        cout << "该有向图有回路，找不到拓扑序列" << endl;
    } else {
        cout << "拓扑序列为：";
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    }

    return 0;
}