LightOJ - 1009 - Back to Underworld --- using DFS

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define scI(n) scanf("%d", &n)
8. #define S 20003
9. using namespace std;
10.  
11. vector <int> Node[S];
12. int n, vis[S], color[S], have[S];
13. int B, W, N, cnB, cnW;
14.  
15. void dfs(int src){
16.     if(vis[src])return;
17.     vis[src] = 1;
18.     int sz = Node[src].size();
19.     for(int i = 0; i < sz; i++){
20.         int v = Node[src][i];
21.         if(color[src] == N)color[src] = B, cnB++;
22.         if(color[src] == B && color[v] == N)color[v] = W, cnW++;
23.         if(color[src] == W && color[v] == N)color[v] = B, cnB++;
24.         dfs(v);
25.     }
26. }
27.  
28. int main(){
29.     int t, x, y, cs = 0, mx, ans;
30.     scI(t);
31.     while(t--){
32.         scI(n);
33.         B = 1, W = 0, N = -1;
34.         ans = 0;
35.         memset(color, N, sizeof(color));
36.         memset(vis, W, sizeof(vis));
37.         memset(have, W, sizeof(have));
38.         for(int i = 0; i < n; i++){
39.             scI(x); scI(y);
40.             have[x] = have[y] = 1;
41.             Node[x].push_back(y);
42.             Node[y].push_back(x);
43.         }
44.         printf("Case %d: ", ++cs);
45.         for(int i = 1; i < S; i++){
46.             if(!vis[i] && have[i]){
47.                 cnB = 0, cnW = 0;
48.                 dfs(i);
49.                 mx = (cnB > cnW)?cnB:cnW;
50.                 ans += mx;
51.             }
52.         }
53.         printf("%d\n", ans);
54.         for(int i = 0; i < S; i++)Node[i].clear();
55.     }
56.     return 0;
57. }