Advertisement
saske_7

articulation point finding.cpp

Dec 29th, 2017
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define bound(x,y , i , j) x >= 0 && x < i && y >= 0 && y < j
  6. #define mp make_pair
  7. #define pb push_back
  8. #define pii pair<int , int>
  9. #define M 500000
  10. #define rep(i , n) for(i = 0 ; i< n ;i++ )
  11. #define repi(i , n ) for(i = 0 ; i<= n ; i++ )
  12. #define mem(x , y ) memset(x , y , sizeof x )
  13. #define mx 5000000
  14. #define ff first
  15. #define ss second
  16.  
  17. int dx[] = { -1 ,+1, 0 , 0 , -1 , -1  , 1 , 1 };
  18. int dy[] = { 0 , 0, +1, -1  , +1 , -1 , 1 , -1 };
  19.  
  20. //int dx[] = { 1 , 1, 2 , 2  , -1 , -1 , -2 , -2 }; // knight direction
  21. //int dy[] = { 2 , -2, +1, -1 ,2 , -2 , 1 , -1 };
  22. vector<int >g[M ] ;
  23. int par[M] , low[M] ,d[M ] , _time  ;
  24. bool vis[M ]  , arr[M ];
  25. map<pii , int > m ;
  26. vector<pii> edge ;
  27.  
  28. void clr(){
  29.     int i ; _time = 0 ;
  30.     rep(i , M ) g[i].clear();
  31.     mem(vis, false  ); mem(low , 0 ) ; rep(i, M) par[i] = i ;
  32.     mem(arr , false );
  33.     m.clear() ;
  34.     edge.clear() ;
  35. }
  36.  
  37. void dfs(int u ){
  38.   int i ,j  , k ;
  39. vis[u] = true ;
  40. int child = 0 ;
  41.  
  42.     ++_time ;
  43.     d[u] = low[u] =  _time ;
  44.  
  45.     rep(i , g[u].size()){
  46.         int v = g[u][i ] ;
  47.         if( u == par[v ] )  continue ;
  48.  
  49.         if(vis[v] ==  true ){       //backedge
  50.             low[u] =  min(d[v] , low[u] ) ;
  51.         }
  52.         else{
  53.             par[v] = u ;
  54.             dfs(v );
  55.  
  56.             low[u] =  min(low[u] , low[v ]) ;
  57.             child++;
  58.             if( d[u] <= low[v] && u != 1 ){
  59.                 arr[u] = true ;
  60.         //      if(u > v ) edge.pb(mp(v , u ));
  61.             //  else edge.pb(mp(u , v ) );
  62.  
  63.             }
  64.  
  65.             if(u == 1 && child > 1  ){
  66.         //      if(u > v ) edge.pb(mp(v , u ));
  67.             //  else edge.pb(mp(u , v ) );
  68.  
  69.                 arr[u] =  true ;
  70.             }
  71.  
  72.         }
  73.     }
  74. }
  75.  
  76. int main(){
  77.     freopen("in.txt","r",stdin );
  78.  
  79. int i , j , k ,cs = 0  , tc ;
  80.     scanf("%d",&tc );
  81.     while(tc--){
  82.     clr();
  83.     int n , qr ;
  84.     scanf("%d %d" , &n , &qr );
  85.     while(qr--){
  86.         int u , v;
  87.         scanf("%d%d",&u , &v );
  88.         g[u].pb(v );
  89.         g[v].pb(u );
  90.  
  91.     }
  92.  
  93.         dfs(1);
  94.   //  rep(i , edge.size() ) printf("%d %d\n", edge[i].ff , edge[i].ss);
  95.     int c =  0;
  96.     rep(i , n ) if(arr[i+1] ==  true )  c++;
  97.  
  98.     //printf("art %d\n", i+1);
  99.         printf("Case %d: %d\n",++cs  ,c );
  100.     }
  101.  
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement