lightoj(1291).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 sf1(a)  scanf("%d ",&a );
#define M 10005
#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 ] ;
vector<pii > bridge ;

int d[M], vis[M], _time, low[M ], par[M ], _count, num ;
int arr[M], track[M]  ;

void clr()
{
    int i ;
    _count =  0  ;
    mem(arr, 0 );
    rep(i, M )
    {
        g[i].clear() ;
        track[i] = par[i] =  i ;
    }
    mem(vis, -1 );
    mem(d, 0) ;
    mem(low, 0 ) ;
    bridge.clear();
}

int find(int a )
{
// printf("find %d %d\n", par[a]);
    if(par[a] ==  a) return a ;
    else return par[a] =  find(par[a]) ;

}
void make(int a, int b )
{
    int u = find(a );
    int v = find(b );
//  printf("received %d %d %d %d\n", a , b , u ,v);
    if(u != v )
    {
        par[u] =  v ;
        //  printf("par %d %d %d \n", u , v ,par[u]) ;
    }
}

void dfs(int u )
{
    int i ;
    ++_time  ;
    d[u] = low[u] =  _time ;

    vis[u] = 1;

    rep(i,g[u].size() )
    {
        int v = g[u][i ];
        if( v == track[u] ) continue  ;
        if(vis[v] !=  -1  )
        {
            low[u] = min(low[u], d[v] );
            // backedge
        }
        else
        {
            track[v] = u ;
            dfs(v ) ;

            low[u] =  min(low[v], low[u] );
            if(d[u] < low[v]  )
            {
                bridge.pb(mp(u, v));
                int hh = bridge.size() -1 ;
                //  printf("bridge %d %d\n", bridge[hh].ff , bridge[hh].ss ) ;
            }
            else
            {
                //  printf("herre %d %d %d %d\n", u , v , par[u] , par[v]);

                make(u, v);

            }
        }
    }
}

int main()
{

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

    int i, j, k, cs= 0, tc ;
    sf1(tc ) ;

    while(tc-- )
    {
        clr();
        int n, qr ;
        scanf("%d%d", &n, &qr );

        while(qr--)
        {
            scanf("%d%d",&i, &j ) ;

            g[i].pb(j );
            g[j].pb(i );

        }

        dfs(0) ;
        //  rep(i , n) {
        //  printf("%d ", find(i));
        //}
        //printf("\n\n");
        rep(i, bridge.size() )
        {
            int u =  find( bridge[i].ff);
            int v =  find( bridge[i].ss);
            //    printf("u v %d %d\n", u , v);
            arr[u]++ ;
            arr[v ]++;

        }
        //  printf("after dfs \n") ;
        k =  0 ;

        rep(i, n ) if(arr[i] ==  1) k++ ;

        k++;
        k/=2;
        printf("Case %d: %d\n",++cs, k );
    }

    return 0;
}