题目
link
题目描述
见链接
输入格式
见链接
输入
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
思路
拓扑排序,但是要计算路径的条数
生产者入度in
必定为0,食物链的末端出度out
必定为0
起点必有一条路径,也就是初始入度为0的点必定有一条路径,以这些点为前驱的点,得到的路径自然是前驱的路径数加上自身的路径数
(为什么不是前驱的路径数+1呢?因为可能某个点,会通过不同的路径走到,单纯加1的话,便是没有计算到这种情况,例如有路径1->2->3
,5->2
,5->3
,画图就可以理解)
那么最后计算所有有入度(单个点不算一条食物链),且出度为0的点的路径之和,就是答案
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<set>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e5+5;
int n,m;
int h[N],e[N],ne[N],idx;
int in[N],out[N],backup[N];
int cnt[N];
bool st[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void topo(){
queue<int> q;
for(int i=1;i<=n;i++)
if(in[i]==0){
cnt[i]=1;
q.push(i);
}
while(q.size()){
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
in[j]--;
cnt[j]+=cnt[t];
if(in[j]==0)
q.push(j);
}
}
}
int main(void){
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
out[a]++;
in[b]++;
}
memcpy(backup,in,sizeof in);
topo();
int ans=0;
for(int i=1;i<=n;i++)
if(out[i]==0&&backup[i])
ans+=cnt[i];
printf("%d\n",ans);
return 0;
}
/*
* When ability does not derserve ambition, just keep moving
*/