SHARE
TWEET

lightoj - 1009 - Back to Underworld (DFS)

jakaria_hossain Sep 7th, 2019 (edited) 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define S 20004
  4. vector<int>Node[S];
  5. int n, color[S],vis[S],have[S],W,B,N,cnB,cnW;
  6. void dfs(int src)
  7. {
  8.     if(vis[src])return;
  9.     vis[src]=1;
  10.     int sz= Node[src].size();
  11.     for(int i=0;i<sz;i++)
  12.     {
  13.         int v= Node[src][i];
  14.         if(color[src]==N)
  15.         {
  16.             color[src]=B;
  17.             cnB++;
  18.         }
  19.         if(color[src]==B && color[v]==N)
  20.         {
  21.             color[v]=W;
  22.             cnW++;
  23.         }
  24.         if(color[src]==W && color[v]==N)
  25.         {
  26.             color[v]=B;
  27.             cnB++;
  28.         }
  29.         dfs(v);
  30.     }
  31. }
  32.  
  33. int main()
  34. {
  35.     int x,y,t,c;
  36.     scanf("%d",&t);
  37.     for(c=1;c<=t;c++)
  38.     {
  39.         int ans=0;
  40.         B=1,W=0,N=-1;
  41.         memset(color,N,sizeof(color));
  42.         memset(vis,W,sizeof(vis));
  43.         memset(have,W,sizeof(have));
  44.         scanf("%d",&n);
  45.         for(int i=0;i<n;i++)
  46.         {
  47.             scanf("%d %d",&x,&y);
  48.             have[x]=have[y]=1;
  49.             Node[x].push_back(y);
  50.             Node[y].push_back(x);
  51.         }
  52.         for(int i=1;i<S;i++)
  53.         {
  54.             if(!vis[i] && have[i])
  55.             {
  56.                 cnB=0,cnW=0;
  57.                 dfs(i);
  58.                 ans+=(max(cnB,cnW));
  59.             }
  60.         }
  61.         printf("Case %d: %d\n",c,ans);
  62.         for(int i=0;i<S;i++)Node[i].clear();
  63.     }
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top