比赛 |
防止浮躁的小练习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);
- }
-