Advertisement
Eather

UVA 459- graph connectivity

Apr 6th, 2011
795
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<vector>
  5. #include<algorithm>
  6. #include<map>
  7. #include<stack>
  8. #include<queue>
  9. #include<cstring>
  10. #include<set>
  11.  
  12. using namespace std;
  13.  
  14. #define MEM(array,w) memset((array),w,sizeof((array)))
  15.  
  16.  
  17. int visited[26];
  18. int visit[26][26];
  19.  
  20. char ch;
  21.  
  22.  
  23. int dfs(int i)
  24. {
  25.     visited[i]=1;
  26.  
  27.     for(int j=0;j<=ch-'A';j++)
  28.     {
  29.         if(visited[j]==0 && visit[i][j]==1)
  30.         {
  31.             dfs(j);
  32.         }
  33.     }
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39.     int test;
  40.  
  41.     cin>>test;
  42.     getchar();
  43.  
  44.  
  45. bool f=0;
  46.  
  47.     while(test--)
  48.     {
  49.         if(f==1)cout<<endl;f=1;
  50.         cin>>ch;
  51.        
  52.         getchar();
  53.  
  54.         MEM(visit,0);
  55.  
  56.         memset(visited,0,sizeof(visited));
  57.  
  58.         while(1)
  59.         {
  60.             string s;
  61.             getline(cin,s);
  62.  
  63.             if(s.size()==0)break;
  64.  
  65.             visit[(s[0]-'A')][(s[1]-'A')]= 1;
  66.             visit[(s[1]-'A')][(s[0]-'A')]= 1;
  67.  
  68.         }
  69.        int sum=0;
  70.  
  71.         for(int i=0;i<=(ch-'A');i++){
  72.  
  73.             if(visited[i]!=1){dfs(i);sum++;}
  74.         }
  75.         cout<<sum<<endl;
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement