题解 | #食物链计数#

首先题目可以抽象成：给定一个DAG，求 $d_{in}=0$ 到 $d_{out}=0$ 的节点的路径的数量。

之后，对于所有节点 $v$ ，记 $cnt[v]$ 为 $d_{in}$ 为0的节点到 $v$ 的路径数量，那么答案就为 $\sum_{d_{out}[u]=0\\d_{in}[u]\ne0} cnt[u]\\$

（注，需要注意孤立点不算链，所以除了 $d_{out}[u]=0$ ，还有加上个 $d_{in}[u]\ne0$ ）

再考虑 $cnt$ 的状态转移， $cnt[v] = \sum_{u\rightarrow v} cnt[u]$ ，因此一个节点的cnt依赖于所有指向该节点的节点，因此计算的顺序需要是拓扑序。

AC Code

#include <iostream>
#include <numeric>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1, vector<int>());
    vector<int> in(n + 1, 0), out(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        in[v]++, out[u]++;
    }
    
    vector<int> cnt(n + 1, 0);

toposort:
    [in, n, &cnt, &adj]()mutable {
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                q.push(i);
                cnt[i] = 1;
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                cnt[v] += cnt[u];
                if (--in[v] == 0) q.push(v);
            }
        }
    }
    ();

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (out[i] == 0 && in[i] != 0) ans += cnt[i];
    }
    cout << ans;

}
// 64 位输出请用 printf("%lld")

注

代码中拓扑排序的lambda函数里的mutable是为了解决in[v]--报错的问题。因为一般情况下的lambda的值捕获将复制一个只读的副本。