用C++实现用栈的拓扑排序

拓扑排序是对有向图进行排序的一种方法，可以用来解决诸如任务调度等问题。栈可以用来存储入度为0的节点，因此可以用栈来实现拓扑排序。

以下是用C++实现用栈的拓扑排序的示例代码：

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

void topologicalSort(vector<vector<int>>& graph, vector<int>& inDegree) {
    stack<int> s;
    int n = graph.size();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            s.push(i);
        }
    }
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        cout << cur << " ";
        for (int next : graph[cur]) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                s.push(next);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {3},
        {3},
        {}
    };
    vector<int> inDegree = {0, 1, 1, 2};
    topologicalSort(graph, inDegree); // 输出：0 1 2 3
    return 0;
}

在上面的示例代码中，我们首先遍历所有节点，将入度为0的节点压入栈中。然后，每次从栈中弹出一个节点，输出该节点，并将该节点指向的所有节点的入度减1。如果减1后某个节点的入度为0，则将该节点压入栈中。重复此过程直到栈为空，即可得到拓扑排序的结果。