LightOJ - 1009 - Back to Underworld --- using BFS

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define scD(n) scanf("%lf", &n)
9. #define scS(n) scanf("%s", &n)
10. #define S 20003
11. #define SS 100003
12. using namespace std;
13. typedef long long LL;
14.  
15. vector <int> race[S], edge;
16. int ans[S], check[S];
17.  
18. int BFS(int src){
19.     int anss = 0;
20.     queue <int> Q;
21.     Q.push(src);
22.     int sz = edge.size();
23.     ans[src] = 1;
24.     while(!Q.empty()){
25.         int x, y;
26.         x = Q.front();
27.         check[x]++;
28.         Q.pop();
29.         y = race[x].size();
30.         for(int i = 0; i < y; i++){
31.             if(!ans[race[x][i]]){
32.                 Q.push(race[x][i]);
33.                 if(ans[x] == 1)ans[race[x][i]] = 2;
34.                 if(ans[x] == 2)ans[race[x][i]] = 1;
35.             }
36.         }
37.         if(Q.empty()){
38.             int vamp = 0, lyk = 0;
39.             for(int i = 0; i < S; i++){
40.                     if(ans[i] == 1)vamp++;
41.                     if(ans[i] == 2)lyk++;
42.                     ans[i] = 0;
43.             }
44.             anss += max(vamp, lyk);
45.             for(int i = 0; i < sz; i++){
46.                 if(check[edge[i]] == 1){
47.                     Q.push(edge[i]);
48.                     ans[edge[i]] = 1;
49.                     break;
50.                 }
51.             }
52.         }
53.     }
54.     return anss;
55. }
56.  
57. void Do(){
58.     int t, n, u, v, cs = 0;
59.     sc(t);
60.     while(t--){
61.         sc(n);
62.         memset(ans, 0, sizeof(ans));
63.         memset(check, 0, sizeof(check));
64.         for(int i = 0; i < S; i++)race[i].clear();
65.         edge.clear();
66.         while(n--){
67.             sc(u);
68.             sc(v);
69.             if(!check[u])check[u] = 1, edge.push_back(u);
70.             if(!check[v])check[v] = 1, edge.push_back(v);
71.             race[u].push_back(v);
72.             race[v].push_back(u);
73.         }
74.         int members = BFS(u);
75.         printf("Case %d: %d\n", ++cs, members);
76.     }
77. }
78.  
79. int main(){
80.     ios_base::sync_with_stdio(0); cin.tie(0);
81.     #ifndef ONLINE_JUDGE
82.     ///freopen("contest.txt","w",stdout);
83.     #endif
84.     Do();
85.     return 0;
86. }