比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 NVIDIA 运行时间 0.299 s
代码语言 C++ 内存使用 9.64 MiB
提交时间 2016-10-27 17:46:13
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstring>
  3. using namespace std;
  4. bool chudu[100100]={0};
  5. bool rudu[100100]={0};
  6. int sumt[100100]={0};
  7. int head[500100]={0};
  8. int ans=0;
  9. struct node{
  10. int to,next;
  11. node()
  12. {
  13. to=next=0;
  14. }
  15. }a[900100];
  16. int tot=0,N,M;
  17. void add(int from,int to)
  18. {
  19. tot++;
  20. a[tot].to=to;
  21. a[tot].next=head[from];
  22. head[from]=tot;
  23. }
  24. void DFS(int node,int y)
  25. {
  26. if(sumt[node]!=0)return;
  27. if(!chudu[node])
  28. {
  29. sumt[y]++;
  30. return;
  31. }
  32. for(int i=head[node];i!=-1;i=a[i].next)
  33. {
  34. DFS(a[i].to,node);
  35. sumt[node]+=sumt[a[i].to];
  36. }
  37. if(y==0)ans+=sumt[node];
  38. }
  39. void read(int &q)
  40. {
  41. int ch=0,x=0;
  42. while(ch=getchar(),ch<'0'||ch>'9');
  43. x=ch-48;
  44. while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
  45. q=x;
  46. }
  47. int main()
  48. {
  49. freopen("chain_2016.in","r",stdin);
  50. freopen("chain_2016.out","w",stdout);
  51. memset(head,-1,sizeof(head));
  52. scanf("%d%d",&N,&M);
  53. for(int i=1;i<=M;i++)
  54. {
  55. int a,b;
  56. read(a);read(b);
  57. add(a,b);
  58. chudu[a]=1;
  59. rudu[b]=1;
  60. }
  61. int tot=0;
  62. for(int i=1;i<=N;i++)
  63. {
  64. if(!rudu[i]&&chudu[i])DFS(i,0);
  65. }
  66. printf("%d",ans);
  67. }
  68.