shipu_a

Div 2 Problem H

Jan 15th, 2013
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3.  
  4. using namespace std;
  5.  
  6. bool visit[15];
  7. vector<int>edge[15];
  8.  
  9. void dfs(int node)
  10. {
  11.     visit[node]=true;
  12.     for(int j=0;j<edge[node].size();j++)
  13.         if(!visit[edge[node][j]])
  14.             dfs(edge[node][j]);
  15. }
  16.  
  17. int main()
  18. {
  19.     int testCase,CaseNo=1,points,u,v,cnt=0;
  20.  
  21.     cin>>testCase;
  22.     while(testCase--)
  23.     {
  24.         cin>>points;
  25.         for(int i=0;i<points;i++)
  26.         {
  27.             cin>>u>>v;
  28.             edge[u].push_back(v);
  29.             edge[v].push_back(u);
  30.         }
  31.  
  32.         for(int i=1;i<=points;i++)
  33.             if(!visit[i])
  34.             {
  35.                 cnt++;
  36.                 dfs(i);
  37.             }
  38.         cout<<"Case "<<CaseNo++<<": "<<cnt<<endl;
  39.         //clear
  40.         cnt=0;
  41.         for(int i=1;i<=points;i++)
  42.         {
  43.             visit[i]=false;
  44.             edge[i].clear();
  45.         }
  46.     }
  47. }
Advertisement
Add Comment
Please, Sign In to add comment