比赛 |
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;
}