NC20000. [HAOI2016]食物链
描述
输入描述
第一行两个整数n和m,接下来m行每行两个整数ai，bi描述m条能量流动关系。 （数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）1 ≤ N ≤ 100000，0 ≤ m ≤ 200000题目保证答案不会爆 int
输出描述
一个整数即食物网中的食物链条数
示例1
输入:
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
C++ 解法, 执行用时: 54ms, 内存消耗: 7052K, 提交时间: 2022-01-17 14:04:11
#include<bits/stdc++.h>
using namespace std;
int n,m;
int chu[100005];
int ru[100005];
vector<int>p[100005];
int dp[100005];
int dfs(int k){
if(!chu[k])return 1;
if(dp[k])return dp[k];
for(int i=0;i<p[k].size();i++){
dp[k]+=dfs(p[k][i]);
}
return dp[k];
}
int main(){
cin>>n>>m;
int t1,t2;
for(int i=1;i<=m;i++){
scanf("%d %d",&t1,&t2);
chu[t2]++;
ru[t1]++;
p[t2].push_back(t1);
}
int ans=0;
for(int i=1;i<=n;i++){
dfs(i);
if(!ru[i])ans+=dp[i];
}
cout<<ans;
return 0;
}