1021 - 拓扑排序+dp- 食物链「HAOI2016」

食物链

描述

如图所示为某生态系统的食物网示意图，据图回答此题。

输入

第一行两个整数 n 和 m ,接下来 m 行每行两个整数 ai bi描述 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

提示

数据范围与提示

1≤N≤100000,0≤m≤200000

保证答案不会超过 int 的最大值

分析

一眼网络流……
然后模拟了一下样例，我可能刚刚眼瞎了
但也就是在模拟样例的时候就胡出了正解–>拓扑排序
辅以递推的思想，就搞完啦

代码

#include<bits/stdc++.h>
#define in  read()
#define N 100009
#define M 4000009 
using namespace std;
inline int read(){
	char ch;int f=1,res=0;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return f==1?res:-res;
}
int n,m,du[N],chu[N],f[N];
int nxt[M],to[M],head[N],cnt=0;
void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}


int main(){
	n=in;m=in;
	int i,j,k;
	for(i=1;i<=m;++i){
		int a=in;int b=in;
		add(a,b);du[b]++;chu[a]++;
	}
	stack<int> S;
	for(i=1;i<=n;++i){
		if(!du[i]&&chu[i]){
			f[i]=1;
			S.push(i);
		}
	}
	int ans=0;
	while(!S.empty()){
		int u=S.top();S.pop();
		int tag=0;
		for(int e=head[u];e;e=nxt[e]){
			tag=1;
			int v=to[e];
			f[v]+=f[u];
			du[v]--;
			if(!du[v]) S.push(v);
		}
		if(!tag){
			ans+=f[u];
		}
	}
	cout<<ans;
	return 0;
}