articulation point finding.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 ;

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

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

        if(vis[v] ==  true ){       //backedge
            low[u] =  min(d[v] , low[u] ) ;
        }
        else{
            par[v] = u ;
            dfs(v );

            low[u] =  min(low[u] , low[v ]) ;
            child++;
            if( d[u] <= low[v] && u != 1 ){
                arr[u] = true ;
        //      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 ;
            }

        }
    }
}

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 %d" , &n , &qr );
    while(qr--){
        int u , v;
        scanf("%d%d",&u , &v );
        g[u].pb(v );
        g[v].pb(u );

    }

        dfs(1);
  //  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);
        printf("Case %d: %d\n",++cs  ,c );
    }

    return 0;
}