C++实现有向图的拓扑排序代码

以下是使用邻接表实现有向图拓扑排序的C++代码示例：

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

using namespace std;

class Solution {
public:
    vector<int> topologicalSort(int numCourses, vector<pair<int, int>>& prerequisites) {
        // 初始化邻接表和入度数组
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        for (auto& pre : prerequisites) {
            graph[pre.second].push_back(pre.first);
            ++inDegree[pre.first];
        }
        // 将入度为0的顶点加入队列中
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        // 拓扑排序
        vector<int> res;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            res.push_back(cur);
            for (auto neighbor : graph[cur]) {
                --inDegree[neighbor];
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        // 判断是否有环
        if (res.size() != numCourses) {
            return {};
        }
        return res;
    }
};

int main() {
    Solution s;
    int numCourses = 4;
    vector<pair<int, int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
    vector<int> res = s.topologicalSort(numCourses, prerequisites);
    for (auto course : res) {
        cout << course << " ";
    }
    cout << endl;
    return 0;
}

其中，拓扑排序算法的步骤如下：

1. 初始化邻接表和入度数组。遍历所有的先决条件，将后续课程添加到先决条件课程的邻接表中，并增加后续课程的入度。

2. 将入度为0的顶点加入队列中。

3. 拓扑排序。从队列中取出一个顶点，将该顶点加入排序结果中，遍历该顶点的所有相邻顶点，将相邻顶点的入度减1，如果相邻顶点的入度为0，则将其加入队列中。

4. 判断是否有环。如果排序结果中的顶点数不等于总顶点数，则说明有环存在，返回空结果。

时间复杂度为O(V+E)，其中V为顶点数，E为边数。