Advertisement
saske_7

lightoj(1026)/bridge finding(bidirectional graph).cpp

Dec 29th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.80 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.    // printf("visiting %d\n", u);
  42.  
  43.     ++_time ;
  44.     d[u] = low[u] =  _time ;
  45.  
  46.     rep(i , g[u].size()){
  47.         int v = g[u][i ] ;
  48.  
  49.         if( v == par[u ] ){
  50.      //   printf("par %d %d\n", u ,v );
  51.         continue ;
  52.     }
  53.  
  54.         if(vis[v] ==  true ){       //backedge
  55.             low[u] =  min(d[v] , low[u] ) ;
  56.     //  printf("backedge %d %d\n", u , v );
  57.         }
  58.         else{
  59.             par[v] = u ;
  60.             dfs(v );
  61.      // printf("\n\nworking on edge %d\n" , u );
  62.             low[u] =  min(low[u] , low[v ]) ;
  63.             child++;
  64.             if( d[u] < low[v]  ){
  65.                 arr[u] = true ;
  66.        // printf("edge %d(%d)  %d(%d)\n" , u , d[u]  , v , low[v] );
  67.                 if(u > v ) edge.pb(mp(v , u ));
  68.                 else edge.pb(mp(u , v ) );
  69.  
  70.             }
  71. /*
  72.             if(u == 1 && child > 1  ){
  73.                 if(u > v ) edge.pb(mp(v , u ));
  74.                 else edge.pb(mp(u , v ) );
  75.  
  76.                 arr[u] =  true ;
  77.             }
  78. /*/
  79.         }
  80.     }
  81. }
  82.  
  83.  
  84. void in(int &i , int &j  ){
  85.  
  86. scanf("%d" , &i) ;
  87.   while(1){
  88.       char c = getchar() ;
  89.       if(c == '(') break ;
  90.  
  91.   }
  92.   scanf("%d", &j );
  93.   while(1){
  94.       char c = getchar() ;
  95.       if(c == ')') break ;
  96.  
  97.   }
  98.  
  99. return ;
  100. }
  101.  
  102. bool comp(pii a , pii b ){
  103.   if( a.ff !=  b.ff) return  a.ff < b.ff ;
  104.   else return a.ss < b.ss ;
  105.  
  106. }
  107.  
  108. int main(){
  109.     //freopen("in.txt","r",stdin );
  110.  
  111. int i , j , k ,cs = 0  , tc ;
  112.     scanf("%d",&tc );
  113.     while(tc--){
  114.     clr();
  115.     int n , qr ;
  116.   scanf("%d",&n );
  117.     rep(i , n ){
  118.       int u ,v  ;
  119.       in(u , k );
  120.  
  121.       rep(j , k ) {
  122.         scanf("%d",&v );
  123.         g[u].pb( v);
  124.         g[v].pb( u);
  125.  
  126.       }
  127.     }
  128.     rep(i , n ) if(vis[i] ==  false ) dfs(i);
  129.     sort(edge.begin() , edge.end() ,comp );
  130.     printf("Case %d:\n%d critical links\n",++cs  ,edge.size() );
  131.  
  132.     rep(i , edge.size() ) printf("%d - %d\n", edge[i].ff , edge[i].ss);
  133.     int c =  0;
  134.    // rep(i , n ) if(arr[i+1] ==  true )  c++;
  135.  
  136.     //printf("art %d\n", i+1);
  137.     }
  138.  
  139.     return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement