题解 P3183 【[HAOI2016]食物链】

佚名 5年前 (2019-04-13) 随笔 567人围观抢沙发百度已收录

#include<bits/stdc++.h>
using namespace std;
int out[100005],in[100005],head[2000005],ver[200005],next[200005],f[100005],tot,ans,x,y,n,m;
void add(int x,int y){
    ver[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
} 
int dfs(int x){
    if (f[x]) return f[x];
    if (out[x]==0) return 1;
    int tmp=0;
    for (int i=head[x];i;i=next[i]) tmp+=dfs(ver[i]);
    f[x]=tmp;
    return f[x];
} 
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        scanf("%d%d",&x,&y);
        add(x,y);
        out[x]++;
        in[y]++;
    }
    for (int i=1;i<=n;i++)
        if (in[i]==0&&out[i]!=0) ans+=dfs(i);
    printf("%d\n",ans); 
    return 0;
}