设计算法求解有向无环图的所有拓扑序列。用C++写出代码

拓扑排序算法可以解决有向无环图（DAG）的拓扑排序问题，即对于一个 DAG，找到一种线性排序，使得对于任意一条有向边 (u, v)，结点 u 在排序结果中都出现在结点 v 的前面。

以下是基于 Kahn 算法的 C++ 代码实现：

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

using namespace std;

const int MAXN = 1e5 + 5;
vector<int> graph[MAXN]; // 存储图的邻接表
int inDegree[MAXN]; // 存储每个节点的入度

vector<vector<int>> allTopoSort(int n) {
    vector<vector<int>> res; // 存储所有拓扑序列的结果
    queue<int> q; // 存储入度为 0 的节点
    vector<int> topoOrder; // 存储当前的拓扑序列

    // 初始化入度为 0 的节点
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // BFS 搜索入度为 0 的节点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 判断是否存在拓扑序列
    if (topoOrder.size() == n) {
        res.push_back(topoOrder);
    }

    // 枚举入度为 0 的节点，从图中删除它并递归求解
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            for (int v : graph[i]) {
                inDegree[v]++;
            }
            inDegree[i] = -1;
            vector<vector<int>> subRes = allTopoSort(n);
            for (vector<int>& subOrder : subRes) {
                subOrder.insert(subOrder.begin(), i);
                res.push_back(subOrder);
            }
            inDegree[i] = 0;
            for (int v : graph[i]) {
                inDegree[v]--;
            }
        }
    }

    return res;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读入有向图，构建邻接表并计算每个节点的入度
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        inDegree[v]++;
    }

    // 求解所有拓扑序列
    vector<vector<int>> res = allTopoSort(n);

    // 输出所有拓扑序列
    for (vector<int>& topoOrder : res) {
        for (int u : topoOrder) {
            cout << u << " ";
        }
        cout << endl;
    }

    return 0;
}

该算法的时间复杂度为 $\mathcal{O}(n \cdot n!)$，其中 $n$ 是节点数。