题目大意
现在给你n个物种和m条能量流动关系，求其中的食物链条数。
物种的名称为从1到n的编号。
m条能量流动关系形如
(a_1 b_1)
(a_2 b_2)
(a_3 b_3)
(a_4 b_4)
...
(a_m b_m)
其中(a_i b_i)表示能量从物种(a_i)流向物种(b_i) 。注意单独的一种孤立生物不算一条食物链。
输入格式
第一行两个整数n和m,接下来m行每行两个整数(a_i b_i)描述m条能量流动关系。
（保证输入数据符合生物学特点，即不存在环，且不会有重复的能量流动关系出现）
输出格式
一个整数，即食物网中的食物链条数。
样例
样例输入
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9
样例输出
9
算法分析：
- 这是一个很裸的图论的题了（考试爆零真的是我的原因了）
- 其实真的很裸没啥可分析的………………
- 跑拓扑或者dfs都行
- 直接看代码吧
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int cnt,n,m;
int head[maxn],rd[maxn],cd[maxn],dp[maxn];
struct edge{int to,next;}a[maxn];
void add(int x,int y){
a[++cnt].to = y;
a[cnt].next = head[x];
head[x] = cnt;
}
queue<int> q;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;++i){
int x,y;scanf("%d%d",&x,&y);
rd[y]++;//入度
cd[x]++;//出度
add(x,y);
}
for(int i = 1;i <= n;++i){
if(!rd[i]){//没有入度说明是根节点
q.push(i);
if(cd[i] != 0)dp[i] = 1;//如果不是叶子节点 就将链数置为1
}
}
while(!q.empty()){
int x = q.front();//取出队首
q.pop();
for(int i = head[x];i;i = a[i].next){//依次遍历队首每一个儿子
dp[a[i].to] += dp[x];//儿子的链数 += 父亲的链数（自己想为啥吧 要不然就画图）
rd[a[i].to] -= 1;//减去当前父亲的入度 已经计算过了 方便再以这个儿子跑拓扑
if(rd[a[i].to] == 0){//类似于深搜 将没有入度的点入队
q.push(a[i].to);
}
}
}
int ans = 0;
for(int i = 1;i <= n;++i)if(cd[i] == 0)ans += dp[i];//把各个叶子节点的权值加上
printf("%d",ans);
return 0;
}
考试的时候没看懂样例 链数没数过来 呀咦惹
谢谢观看
点个关注 >,<