> ✅ **OJ 验证通过**：Accepted（runid 4115391，2026-08-14 提交于校内 OJ Contest3056） ## 题目大意给定 $n$ 个物种和 $m$ 条能量流动关系（有向边 $a_i \to b_i$，能量从 $a_i$ 流向 $b_i$），求食物网的**食物链条数**。食物链是从入度为 $0$ 的物种出发、到出度为 $0$ 的物种结束的路径，单独一种孤立生物不算一条食物链。$1 \le n \le 10^5$，$0 \le m \le 2 \times 10^5$。 ## 思路分析食物链的本质是 **DAG 上的路径计数**：从"生产者"（入度为 0）到"消费者"（出度为 0）的所有路径。定义 $dp[u]$ 表示**以 $u$ 为起点的食物链条数**。若 $u$ 出度为 0（消费者），则 $dp[u] = 1$；否则： $$ dp[u] = \sum_{u \to v} dp[v] $$ 按**拓扑序的逆序**计算 $dp$（每个节点的 $dp$ 只依赖其后继）。最终答案： $$ \text{ans} = \sum_{u:\ \text{indeg}[u] = 0} dp[u] $$ **易错点**：孤立点（入度、出度都为 0）不算食物链，累加答案时必须跳过（判断 $outdeg[u] > 0$）。 ## 复杂度分析拓扑排序 $O(n + m)$，DP 转移 $O(n + m)$，总复杂度 $O(n + m)$。 ## 参考代码 ```cpp #include using namespace std; typedef long long ll; const int MAXN = 100005; vector g[MAXN]; int indeg[MAXN], indeg0[MAXN], outdeg[MAXN]; ll dp[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; g[a].push_back(b); indeg[b]++; indeg0[b]++; outdeg[a]++; } queue q; for (int i = 1; i <= n; i++) { if (outdeg[i] == 0) dp[i] = 1; // 消费者 if (indeg[i] == 0) q.push(i); } vector topo; while (!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for (int v : g[u]) { if (--indeg[v] == 0) q.push(v); } } // 逆拓扑序计算 dp for (int i = (int)topo.size() - 1; i >= 0; i--) { int u = topo[i]; for (int v : g[u]) dp[u] += dp[v]; } ll ans = 0; for (int u = 1; u <= n; u++) { if (indeg0[u] == 0 && outdeg[u] > 0) ans += dp[u]; // 排除孤立点 } cout << ans << endl; return 0; } ```