fork download
copy 
  1. # include <iostream>
  2. # include <stdio.h>
  3. # include <algorithm>
  4. # include <queue>
  5. # include <set>
  6. # include <string.h>
  7. # include <vector>
  8. # include <fstream>
  9. # include <math.h>
  10. # include <sstream>
  11. # include <stack>
  12.  
  13. # define for1(i,k,n)              for(long long i=k;i<n;i++)
  14. # define for2(i,k,n)              for(long long i=k;i<=n;i++)
  15. # define Min(x,y)                   ((x)<(y)?(x):(y))
  16. # define Max(x,y)                   ((x)>(y)?(x):(y))
  17. # define INF (long long int ) 1e15
  18. # define ALL(x)                  (begin(x),end(x))
  19. # define Abs(x)                 (x>=0?x:-x)
  20.  
  21. using namespace std;
  22. typedef long long int  ll;
  23. ll  time1;
  24. vector < vector< ll> > g;
  25. vector <ll> status;
  26. vector <ll> parent;
  27. vector<ll> child;
  28. vector <bool> check;
  29. vector <ll> low;
  30. vector <ll> in;
  31. void dfs (ll x)
  32. {
  33.     if (status[x]!=0) // so that visited verices are not visited again
  34.         return;
  35.    ll y;  ++time1;// time1 is the dfs number
  36.     in[x]=time1;// in refers to initial or the time of discovery
  37.     low[x]=time1;// low refers to the minimum dfs no that can be acessed by the subtree rooted at x
  38.     status[x]=1;// status [x]=1 since it is benig processesd
  39.     for1(i,0,g[x].size())  // a loop to acess all its neighbours
  40.     {
  41. y=g[x][i];  // one neighbour
  42. if (status[y]==0)
  43. {// a dfs only if it is undiscovered
  44.     parent[y]=x;// stores the parent of y that is x
  45.     ++child[x];//updates the no of children of x
  46.     dfs(y);
  47.     low[x]=Min(low[x],low[y]);// checks for Minimum dfs no that can be acessed by tree at x this is  a recursive function
  48.     if ((parent[x]==-1)&&(child[x]>1))  // initilaised parent of all to be -1 so check if x is a root
  49.         check[x]=true;
  50.     if ((parent[x]!=-1)&&(low[y]>=low[x]))// checks if a non root is an articulation point
  51.         check[x]=true;
  52. }
  53. else if (y!=parent[x])
  54. {
  55.     low[x]=Min(low[x],low[y]);  // continuation of minimum
  56. }
  57.  
  58.  
  59.     }
  60.     status[x]=2;
  61. }
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  int  main()
  70. {
  71.  #ifndef ONLINE_JUDGE
  72.     freopen("in.txt", "r", stdin);
  73. #endif
  74.     std::ios_base::sync_with_stdio (false);
  75.  
  76.     ll i,j,k,x,y,l,n,m,t,sum1;
  77. cin>>t;
  78. while(t--)
  79. {
  80.     cin>>n>>m>>k;
  81.     sum1=0; time1=0;
  82. g.clear();//g stores edges
  83. in.clear();//initial time of discovery
  84. low.clear();// minimum dfs no acessed by the tree rooted
  85. parent.clear();// stores the parent of a vertice
  86. child.clear();// stores the no of children of a vertic
  87. check.clear();//boolean to store if it is an articulation point
  88. status.clear();// to store the condition discovered,undiscovered,processed with undiscovered=0,processed=1,finished=2
  89. g.resize(n);
  90. status.resize(n);
  91. in.resize(n);// resizing all of them to n since there are n vertice
  92. low.resize(n);
  93. parent.resize(n);
  94. child.resize(n);
  95. check.resize(n);
  96.  
  97. fill(parent.begin(),parent.end(),-1);// filling by default for parent to be -1
  98. fill(child.begin(),child.end(),0);// children count =0 for all
  99. fill(check.begin(),check.end(),0);// check =0 or false for all since no art. pnt
  100. fill(status.begin(),status.end(),0);// status=0,or undsicovered
  101.  
  102. for1(i,0,m)
  103. {
  104.     cin>>x>>y;
  105.     g[x].push_back(y);// since undirecred grph x-y =y-x
  106.     g[y].push_back(x);
  107. }
  108. for1(i,0,n)
  109. {
  110.     if (status[i]==0)
  111.         dfs(i);  // dfs for all vertices that are undicovered
  112. }
  113. for1(i,0,n)
  114. {
  115.     if (check[i])
  116.         ++sum1;// if check is true then art. pnt.
  117. }
  118. ll f=sum1*k; //final answer
  119. cout<<f<<endl;
  120. }
  121. return 0;
  122. }
Runtime error #stdin #stdout #stderr 0s 4512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/mGdS8b
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!