题解 | 食物链计数

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int n,m;
map<int,bool> f_eat;
vector<int> plants;
vector<int> G[N];
int r[N],c[N];
int dp[N];
int res;

int dfs(int u){
	if(dp[u]!=0){
		return dp[u];
	}
	
	if(f_eat[u]){
		return 1;
	}
	
	for(int v:G[u]){
		dp[u]+=dfs(v);
	}
	return dp[u];
}

void solve(){
	
	for(int i=0;i<plants.size();i++){
		res+=dfs(plants[i]);
	}	
	
	cout<<res<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		G[u].push_back(v);
		r[v]++;
		c[u]++;
	} 
	
	for(int i=1;i<=n;i++){
		if(r[i]==0&&c[i]==0){
			continue;
		}
		if(r[i]==0){
			plants.push_back(i);
		}
		if(c[i]==0){
			f_eat[i]=true;
		}
	}
	
	solve();

    return 0;
}