原题链接:P3183 [HAOI2016] 食物链。
难度:Easy
。
根据定义,食物链是一个 DAG,所以可以进行拓扑排序。
食物链也就转化成了:图中从一个入度为 \(0\) 的点到一个出度为 \(0\) 的点的路径。
那么只需要拓扑排序求出所有起点到每个点的路径条数,然后累加出度为 \(0\) 的点的值即可。
需要注意的是,单独的一种孤立生物不算一条食物链,所以需要特判一下。
#include <bits/stdc++.h>
const int N = 1e5 + 10;
std::queue<int> q;
std::vector<int> g[N];
int n, m, ans, f[N], d[N][2];
// d[i][0/1] 表示入度/出度
// f[i] 记录以 i 为终点的路径条数
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> n >> m;
for (int i = 0, u, v; i < m; ++i) {
std::cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
++d[u][1], ++d[v][0]; // 更新入度出度
}
for (int i = 1; i <= n; ++i)
if (!d[i][0] && d[i][1]) q.push(i), f[i] = 1; // 入度为 0 且有出度时,才不是孤立生物
while (!q.empty()) { // 拓扑排序
int u = q.front(); q.pop();
for (auto v : g[u]) {
f[v] += f[u]; // 此时到 u 的路径都可以通过 <u,v> 到达 v
if (!--d[v][0]) q.push(v);
}
}
for (int i = 1; i <= n; ++i)
if (!d[i][1]) ans += f[i]; // 此时孤立生物 f[i] = 0
std::cout << ans << std::endl;
return 0;
}
标签:std,食物链,int,题解,出度,入度,LGP3183,cin
From: https://www.cnblogs.com/oier-wst/p/18427905/luogu-P3183-solution