unlucky_13

uva_869

Jun 16th, 2013
40
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. /*
  2.  Author                             :     unlucky_13
  3.  Problem_link                       :
  4.  Category                           : TOO Easy
  5.  Algorithm_Used                     : Disjoint-Set
  6.  */
  7.  
  8. #include<cstdio>
  9. #include<sstream>
  10. #include<cstdlib>
  11. #include<cctype>
  12. #include<cmath>
  13. #include<algorithm>
  14. #include<set>
  15. #include<queue>
  16. #include<stack>
  17. #include<list>
  18. #include<iostream>
  19. #include<fstream>
  20. #include<numeric>
  21. #include<string>
  22. #include<vector>
  23. #include<cstring>
  24. #include<map>
  25. #include<iterator>
  26. #define LL long long int
  27. //const long long int inf = 2147483647 ;
  28. //const int minx=;
  29. const int maxn=200;
  30. using namespace std;
  31. int par[maxn][2] ;
  32. int find(int u,int i){
  33.     if(par[u][i]==u) return u ;
  34.     return par[u][i]= find(par[u][i],i) ;
  35. }
  36.  
  37. int main() {
  38.     freopen("C:\\Users\\Mazhar\\Desktop\\in.txt", "r", stdin);
  39.     int tc ,n;
  40.     char to,from;
  41.     scanf("%d",&tc) ;
  42.     bool blank = false ;
  43.     while(tc--){
  44.         if(blank) printf("\n") ;
  45.         else blank = true ;
  46.         for(int i=0;i<30;i++){
  47.             par[i][0] = par[i][1] = i ;
  48.         }
  49.  
  50.         scanf("%d\n",&n) ;
  51.         for(int i=0;i<n;i++){
  52.             scanf("%c %c\n",&to,&from) ;
  53.             int U = find(to-'A',0) ;
  54.             int V = find(from-'A',0) ;
  55.             if(U!=V) par[U][0]=V ;
  56.         }
  57.  
  58.         scanf("%d\n",&n) ;
  59.         for(int i=0;i<n;i++){
  60.             scanf("%c %c\n",&to,&from) ;
  61.             int U = find(to-'A',1) ;
  62.             int V = find(from-'A',1) ;
  63.             if(U!=V) par[U][1]=V ;
  64.         }
  65.  
  66.         bool res=true ; ;
  67.         for(int i=0;i<30;i++){
  68.             if(find(i,0)!=find(i,1)){
  69.                 res = false ;
  70.                 break ;
  71.             }
  72.  
  73.         }
  74.  
  75.         if(res) printf("YES") ;
  76.         else printf("NO") ;
  77.         printf("\n") ;
  78.     }
  79.  
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment