Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement