算法题：C++求有向无环图的路径数

有向无环图的路径数可以通过拓扑排序和动态规划求解。

假设该有向无环图有 $n$ 个节点，$m$ 条边，$inDegree[i]$ 表示节点 $i$ 的入度，$dp[i]$ 表示从起点到节点 $i$ 的路径总数，则可以按照如下步骤求解：

1. 初始化：将所有入度为 0 的节点的 $dp$ 值赋为 1。

2. 拓扑排序：从入度为 0 的节点开始，依次遍历其出边指向的节点，将这些节点的入度减 1。如果减为 0，则将其加入拓扑序列中。重复该过程直至所有节点都被遍历。

3. 动态规划：按照拓扑序列的顺序，依次更新每个节点的 $dp$ 值。对于每个节点 $i$，遍历其所有入边指向的节点 $j$，将 $dp[j]$ 加到 $dp[i]$ 中。

4. 输出结果：最终 $dp$ 数组中，终点的值即为从起点到终点的路径总数。

以下是 C++ 代码实现：

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

using namespace std;

const int N = 100010;

int n, m;
int inDegree[N], dp[N];
vector<int> edges[N];

void topoSort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!inDegree[i])
            q.push(i), dp[i] = 1;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : edges[u])
        {
            inDegree[v]--;
            if (!inDegree[v])
                q.push(v);
            dp[v] += dp[u];
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        inDegree[b]++;
    }

    topoSort();

    cout << dp[n] << endl;

    return 0;
}