用C++写一个dag管理代码

以下是一个简单的 DAG（有向无环图）管理代码的示例，使用 C++ 实现：

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

using namespace std;

const int MAXN = 10005;

vector<int> edges[MAXN]; // 存储图的边
int in_degrees[MAXN]; // 存储每个节点的入度
int node_num, edge_num; // 节点数和边数

void topsort()
{
    queue<int> q;
    for (int i = 1; i <= node_num; i++)
    {
        if (in_degrees[i] == 0) // 将入度为0的节点入队
        {
            q.push(i);
        }
    }

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << u << " "; // 输出节点 u
        for (int i = 0; i < edges[u].size(); i++)
        {
            int v = edges[u][i];
            in_degrees[v]--; // 将节点 u 的出边的终点入度减1
            if (in_degrees[v] == 0) // 若节点 v 的入度为0，则入队
            {
                q.push(v);
            }
        }
    }
}

int main()
{
    cin >> node_num >> edge_num;

    // 读入边信息
    for (int i = 1; i <= edge_num; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        in_degrees[v]++;
    }

    topsort(); // 执行拓扑排序

    return 0;
}

该代码通过使用邻接表存储图的边和每个节点的入度，实现了 DAG 的拓扑排序。拓扑排序是 DAG 中的一种排序方法，将 DAG 中所有节点按照依赖关系排序，即在 DAG 中，如果节点 A 是节点 B 的前置节点，则节点 A 的排序位置在节点 B 前面。拓扑排序的实现思路是，先将 DAG 中所有入度为0的节点入队，然后依次取出队首节点，将其输出并将其所有出边的终点入度减1，如果终点节点入度为0则入队，直到队列为空。