比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
食物链 |
最终得分 |
100 |
用户昵称 |
swttc |
运行时间 |
0.270 s |
代码语言 |
C++ |
内存使用 |
3.37 MiB |
提交时间 |
2017-05-22 22:55:18 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,inde[100010],oude[100010],ans[100010],inq[100010],anss,indee[100010];
queue<int>qu;
vector<int>e[100010];
void work()
{
for(int i=1;i<=n;i++)
{
if(inde[i]==0&&oude[i]!=0)
{
qu.push(i);
inq[i]=ans[i]=1;
}
}
while(!qu.empty())
{
int u=qu.front();
qu.pop();
inq[u]=0;
for(int i=0;i<e[u].size();i++)
{
ans[e[u][i]]+=ans[u];
inde[e[u][i]]--;
if(inq[e[u][i]]==0&&inde[e[u][i]]==0)
{
qu.push(e[u][i]);
inq[e[u][i]]=1;
}
}
}
return;
}
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 a,b;
scanf("%d%d",&a,&b);
e[a].push_back(b);
inde[b]++;
indee[b]++;
oude[a]++;
}
work();
for(int i=1;i<=n;i++)
{
if(oude[i]==0&&indee[i]!=0)
{
anss+=ans[i];
}
}
printf("%d",anss);
return 0;
}