P3183 [HAOI2016]食物链

题目描述

如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

输入输出格式

输入格式：

第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）1<=N<=100000 0<=m<=200000题目保证答案不会爆 int

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

9
题目大意：求食物链条数
题解:拓扑+递推

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

queue<int>q;
int n,m,ans,sumedge;
int out[100009],in[100009],f[100009],head[100009];

struct Edge{
    int x,y,nxt;
    Edge(int x=0,int y=0,int nxt=0):
        x(x),y(y),nxt(nxt){}
}edge[200008];

void add(int x,int y){
    edge[++sumedge]=Edge(x,y,head[x]);
    head[x]=sumedge;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        in[y]++;out[x]++;
    }
    for(int i=1;i<=n;i++)if(in[i]==0&&out[i])f[i]=1,q.push(i);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].nxt){
            int v=edge[i].y;
            f[v]+=f[now];
            in[v]--;
            if(in[v]==0)q.push(v);
        }
    }
    for(int i=1;i<=n;i++)if(!out[i])ans+=f[i];
    printf("%d
",ans);
    return 0;
}

记忆化搜索逆推

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m,sumedge,ans;

int in[100009],out[100009],head[100009],f[100009];

struct Edge{
    int x,y,nxt;
    Edge(int x=0,int y=0,int nxt=0):
        x(x),y(y),nxt(nxt){}
}edge[200009];

void add(int x,int y){
    edge[++sumedge]=Edge(x,y,head[x]);
    head[x]=sumedge;
}

int dfs(int x){
    if(f[x])return f[x];
    if(in[x]&&!out[x])return 1;
    int js=0;
    for(int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].y;
        js+=dfs(v);
    }
    f[x]=js;
    return f[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        in[y]++;out[x]++;
    }
    for(int i=1;i<=n;i++)
    if(!in[i]&&out[i])ans+=dfs(i);
    printf("%d
",ans);
    return 0;
}