- /****************##### بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم #####******************
- __________________________________________________________________________
- ###################### Ya-Seen Arafat(ACWizard) #########################
- ###################### UAP-CSE-33B #########################
- *************************************************************************/
- #include <bits/stdc++.h>
- #define scI(n) scanf("%d", &n)
- #define S 20003
- using namespace std;
- vector <int> Node[S];
- int n, vis[S], color[S], have[S];
- int B, W, N, cnB, cnW;
- void dfs(int src){
- if(vis[src])return;
- vis[src] = 1;
- int sz = Node[src].size();
- for(int i = 0; i < sz; i++){
- int v = Node[src][i];
- if(color[src] == N)color[src] = B, cnB++;
- if(color[src] == B && color[v] == N)color[v] = W, cnW++;
- if(color[src] == W && color[v] == N)color[v] = B, cnB++;
- dfs(v);
- }
- }
- int main(){
- int t, x, y, cs = 0, mx, ans;
- scI(t);
- while(t--){
- scI(n);
- B = 1, W = 0, N = -1;
- ans = 0;
- memset(color, N, sizeof(color));
- memset(vis, W, sizeof(vis));
- memset(have, W, sizeof(have));
- for(int i = 0; i < n; i++){
- scI(x); scI(y);
- have[x] = have[y] = 1;
- Node[x].push_back(y);
- Node[y].push_back(x);
- }
- printf("Case %d: ", ++cs);
- for(int i = 1; i < S; i++){
- if(!vis[i] && have[i]){
- cnB = 0, cnW = 0;
- dfs(i);
- mx = (cnB > cnW)?cnB:cnW;
- ans += mx;
- }
- }
- printf("%d\n", ans);
- for(int i = 0; i < S; i++)Node[i].clear();
- }
- return 0;
- }
Saturday, June 6, 2015
LightOJ - 1009 - Back to Underworld --- using DFS
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment