比赛 EYOI与SBOI开学欢乐赛9th 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.211 s
代码语言 C++ 内存使用 8.54 MiB
提交时间 2022-09-30 19:14:46
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=100000+5;
struct sf{
    int to,next;
}eg[4*N],eg2[4*N];
int head[N],ne=0;
int head2[N];
int n,m; 
int in[N]={0},out[N]={0};
int tp[N],cnt=0;
int f[N]={0};
void add(int x,int y){
    eg[++ne]={y,head[x]};head[x]=ne;
    eg2[ne]={x,head2[y]};head2[y]=ne;
    in[y]++;out[x]++;
    return ;
}
queue<int>q;
bool vis[N]={0};
int main(){
	freopen ("chain_2016.in","r",stdin);
	freopen ("chain_2016.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
	    int x,y;scanf("%d%d",&x,&y);
	    add(x,y);
    }
    for (int i=1;i<=n;i++){
        if (!in[i])q.push(i),tp[++cnt]=i,f[i]=1,vis[i]=1;
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        for (int i=head[u];i!=0;i=eg[i].next){
            int v=eg[i].to;
            if (!in[v])continue;
            in[v]--;
            if (!in[v])q.push(v),tp[++cnt]=v;
        }
    }
    for (int i=1;i<=n;i++){
        int u=tp[i];
        for (int j=head2[u];j!=0;j=eg2[j].next){
            int v=eg2[j].to;
            f[u]+=f[v];
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++)if (!out[i]&&!vis[i])ans+=f[i];
    printf("%d\n",ans);
    return 0;
}