[DFS]bzoj4562: [Haoi2016]食物链

题目描述

如图所示为某生态系统的食物网示意图,据图回答第1小题

现在给你n个物种和m条能量流动关系,求其中的食物链条数。

物种的名称为从1到n编号

M条能量流动关系形如

a1 b1

a2 b2

a3 b3

……

am-1 bm-1

am bm

其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

输入

第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。

(数据保证输入数据符号生物学特点,且不会有重复的能量流动关系出现)

1<=N<=100000 0<=m<=200000

题目保证答案不会爆 int

输出

一个整数即食物网中的食物链条数

样例输入

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

题解

生物题

易知结束点出度为0,起始点入度为0,DFS一遍,记一下每个点在多少条食物链上,每次往$father$上加即可;

#include<cstdio>
#include<algorithm>
using namespace std;
int N,M,Ans,F[100005];
int tot,_in[100005],_out[100005],son[200005],lnk[100005],nxt[200005];
inline void add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
inline int read(){
    int Res=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res;
}
int dfs(int x){
    if (F[x]) return F[x];
    if (_out[x]==0&&_in[x]!=0) return F[x]=1;
    int &Res=F[x];
    for (int i=lnk[x];i;i=nxt[i]) Res+=dfs(son[i]);
    return Res;
}
int main()
{
    N=read();M=read();
    for (int i=1;i<=M;i++){
        int x=read(),y=read();
        add(x,y);_in[y]++;_out[x]++;
    }
    for (int i=1;i<=N;i++) if (_in[i]==0&&_out[i]!=0) dfs(i),Ans+=F[i];
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注