比赛 |
防止浮躁的小练习v0.7 |
评测结果 |
AAAAAAAAAA |
题目名称 |
食物链 |
最终得分 |
100 |
用户昵称 |
NVIDIA |
运行时间 |
0.299 s |
代码语言 |
C++ |
内存使用 |
9.64 MiB |
提交时间 |
2016-10-27 17:46:13 |
显示代码纯文本
#include<cstdio>
#include<cstring>
using namespace std;
bool chudu[100100]={0};
bool rudu[100100]={0};
int sumt[100100]={0};
int head[500100]={0};
int ans=0;
struct node{
int to,next;
node()
{
to=next=0;
}
}a[900100];
int tot=0,N,M;
void add(int from,int to)
{
tot++;
a[tot].to=to;
a[tot].next=head[from];
head[from]=tot;
}
void DFS(int node,int y)
{
if(sumt[node]!=0)return;
if(!chudu[node])
{
sumt[y]++;
return;
}
for(int i=head[node];i!=-1;i=a[i].next)
{
DFS(a[i].to,node);
sumt[node]+=sumt[a[i].to];
}
if(y==0)ans+=sumt[node];
}
void read(int &q)
{
int ch=0,x=0;
while(ch=getchar(),ch<'0'||ch>'9');
x=ch-48;
while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
q=x;
}
int main()
{
freopen("chain_2016.in","r",stdin);
freopen("chain_2016.out","w",stdout);
memset(head,-1,sizeof(head));
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++)
{
int a,b;
read(a);read(b);
add(a,b);
chudu[a]=1;
rudu[b]=1;
}
int tot=0;
for(int i=1;i<=N;i++)
{
if(!rudu[i]&&chudu[i])DFS(i,0);
}
printf("%d",ans);
}