C++ 实现拓扑排序：使用入度数组和 DFS 算法

是的，你可以通过定义一个数组来记录每个节点的入度，并将入度为 0 的节点压入栈中，然后使用 DFS 算法获取拓扑序列。

首先，你需要定义一个数组来存储每个节点的入度信息，假设节点的数量为 n，那么可以定义一个大小为 n 的数组 inDegree，初始值都为 0。

接下来，你需要遍历所有的边，对于边 (u, v)，将节点 v 的入度加 1，表示有一个节点指向 v。

然后，你可以定义一个栈来存储入度为 0 的节点。遍历所有的节点，将入度为 0 的节点压入栈中。

接下来，你可以使用 DFS 算法来获取拓扑序列。首先从栈中弹出一个节点，打印输出，然后遍历该节点指向的所有节点，将每个节点的入度减 1。如果减 1 后的入度为 0，将该节点压入栈中。重复以上步骤，直到栈为空。

下面是一个示例代码：

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

void dfs(vector<vector<int>>& graph, vector<int>& inDegree, stack<int>& s) {
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << ' '; // 打印输出节点

        for (int i = 0; i < graph[node].size(); i++) {
            int nextNode = graph[node][i];
            inDegree[nextNode]--; // 入度减 1

            if (inDegree[nextNode] == 0) {
                s.push(nextNode); // 入度为 0 的节点压入栈中
            }
        }
    }
}

void topologicalSort(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> inDegree(n, 0);
    stack<int> s;

    // 计算入度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            int node = graph[i][j];
            inDegree[node]++;
        }
    }

    // 将入度为 0 的节点压入栈中
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            s.push(i);
        }
    }

    // 深度优先搜索获取拓扑序列
    dfs(graph, inDegree, s);
}

int main() {
    vector<vector<int>> graph = {{1, 2}, {2, 3}, {4}, {4, 5}, {}};
    topologicalSort(graph);

    return 0;
}

以上代码通过定义一个数组 inDegree 来记录每个节点的入度，使用栈来存储入度为 0 的节点，最终通过 DFS 算法获取拓扑序列并打印输出。