lightoj1009

CODE

#include <bits/stdc++.h>

using namespace std;
vector<int> e[20005];
int ncase,t,num,total,n,tp1,tp2,ans;
int vis[20005];
void dfs(int u,int sta)
{       if(!sta)num++;
        total++;
        vis[u]=1;
        for(int i=0;i<e[u].size();i++)
        {
                int v=e[u][i];
                if(!vis[v])dfs(v,sta^1);
        }
}
int main()
{
        cin >> t;
        while(t--)
        {
                cin >> n;
                ans=0;
                memset(vis,1,sizeof(vis));
                for(int i=1;i<=20000;i++)
                        e[i].clear();
                for(int i=0;i<n;i++)
                {
                        cin >> tp1 >> tp2;
                        vis[tp1]=vis[tp2]=0;
                        e[tp1].push_back(tp2);
                        e[tp2].push_back(tp1);
                }
                for(int i=1;i<=20000;i++)
                {
                        num=0;
                        total=0;
                        if(!vis[i])dfs(i,0);
                        ans+=max(num,total-num);
                }
                cout << "Case "<<++ncase<<": "<<ans<<endl;
        }
        return 0;
}