食物链-牛客（拓扑排序）

食物链都会数吧！从最低端到达最高端称为一条食物链。(高中生物题)，现在有m条关系和n种动物，数关系图中有多少条食物链。

HAOI2016食物链

思路

食物链就是找出哪些点的优先度比较低，而拓扑排序正是比较点与点出现前后关系的算法，所以采用拓扑算法。

• 其中m种关系比较多，所以采用结构体的方法存储关系图。
• rd数组存储的是每个点的入度。cd数组存储的是每个点的出度。
• 最低端的食物一定是入度为0，最高端的食物一定是出度为0。
• sum数组存储的就是以x为最低端的食物时，到达最高端食物时能形成的食物链。当sum[x]不为0时，意味着以x为最低端食物的食物链已经全部找出。

#include<bits/stdc++.h>
#define M  200010
using namespace std;
int head[M];
int rd[M],cd[M];
int sum[M];
int ans,cnt;
struct node
{
    int next;
    int v;
}edge[M];
void init( )
{
    memset(rd,0,sizeof(rd));
    memset(cd,0,sizeof(cd));
    memset(sum,0,sizeof(sum));
    memset(head,-1,sizeof(head));
    cnt=ans=0;
}
void add(int x,int y)
{
    edge[++cnt].next=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
int dfs(int x)
{
    if(cd[x]==0)
    {
        sum[x]++;
    }
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        if(sum[edge[i].v])
        {
            sum[x]+=sum[edge[i].v];
        }
        else
        {
            sum[x]+=dfs(edge[i].v);
        }
    }
    return sum[x];
}
int main( )
{
    init( );
    int x,y;
    int m,n;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        cd[x]++;
        rd[y]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(rd[i]==0&&cd[i]!=0)
        {
            ans+=dfs(i);
        }
    }
    printf("%d\n",ans);
    return 0;
}