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

#include<bits/stdc++.h>

using namespace std;

#define bound(x,y , i , j) x >= 0 && x < i && y >= 0 && y < j
#define mp make_pair
#define pb push_back
#define pii pair<int , int>
#define M 500000
#define rep(i , n) for(i = 0 ; i< n ;i++ )
#define repi(i , n ) for(i = 0 ; i<= n ; i++ )
#define mem(x , y ) memset(x , y , sizeof x )
#define mx 5000000
#define ff first
#define ss second

int dx[] = { -1 ,+1, 0 , 0 , -1 , -1  , 1 , 1 };
int dy[] = { 0 , 0, +1, -1  , +1 , -1 , 1 , -1 };

//int dx[] = { 1 , 1, 2 , 2  , -1 , -1 , -2 , -2 }; // knight direction
//int dy[] = { 2 , -2, +1, -1 ,2 , -2 , 1 , -1 };
vector<int >g[M ] ;
int par[M] , low[M] ,d[M ] , _time  ;
bool vis[M ]  , arr[M ];
map<pii , int > m ;
vector<pii> edge ;

void clr(){
    int i ; _time = 0 ;
    rep(i , M ) g[i].clear();
    mem(vis, false  ); mem(low , 0 ) ; rep(i, M) par[i] = i ;
    mem(arr , false );
    m.clear() ;
    edge.clear() ;
}

void dfs(int u ){
  int i ,j  , k ;
vis[u] = true ;
int child = 0 ;
   // printf("visiting %d\n", u);

    ++_time ;
    d[u] = low[u] =  _time ;

    rep(i , g[u].size()){
        int v = g[u][i ] ;

        if( v == par[u ] ){
     //   printf("par %d %d\n", u ,v );
        continue ;
    }

        if(vis[v] ==  true ){       //backedge
            low[u] =  min(d[v] , low[u] ) ;
    //  printf("backedge %d %d\n", u , v );
        }
        else{
            par[v] = u ;
            dfs(v );
     // printf("\n\nworking on edge %d\n" , u );
            low[u] =  min(low[u] , low[v ]) ;
            child++;
            if( d[u] < low[v]  ){
                arr[u] = true ;
       // printf("edge %d(%d)  %d(%d)\n" , u , d[u]  , v , low[v] );
                if(u > v ) edge.pb(mp(v , u ));
                else edge.pb(mp(u , v ) );

            }
/*
            if(u == 1 && child > 1  ){
                if(u > v ) edge.pb(mp(v , u ));
                else edge.pb(mp(u , v ) );

                arr[u] =  true ;
            }
/*/
        }
    }
}


void in(int &i , int &j  ){

scanf("%d" , &i) ;
  while(1){
      char c = getchar() ;
      if(c == '(') break ;

  }
  scanf("%d", &j );
  while(1){
      char c = getchar() ;
      if(c == ')') break ;

  }

return ;
}

bool comp(pii a , pii b ){
  if( a.ff !=  b.ff) return  a.ff < b.ff ;
  else return a.ss < b.ss ;

}

int main(){
    //freopen("in.txt","r",stdin );

int i , j , k ,cs = 0  , tc ;
    scanf("%d",&tc );
    while(tc--){
    clr();
    int n , qr ;
  scanf("%d",&n );
    rep(i , n ){
      int u ,v  ;
      in(u , k );

      rep(j , k ) {
        scanf("%d",&v );
        g[u].pb( v);
        g[v].pb( u);

      }
    }
    rep(i , n ) if(vis[i] ==  false ) dfs(i);
    sort(edge.begin() , edge.end() ,comp );
    printf("Case %d:\n%d critical links\n",++cs  ,edge.size() );

    rep(i , edge.size() ) printf("%d - %d\n", edge[i].ff , edge[i].ss);
    int c =  0;
   // rep(i , n ) if(arr[i+1] ==  true )  c++;

    //printf("art %d\n", i+1);
    }

    return 0;
}