Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. int n, m, q, T, Ant[100005], F1, F2, t[100005], c[100005], Fant1, Fant2;
  7. string s, s1, s2;
  8. map<string, int> M;
  9.  
  10. int Find( int x )
  11. {
  12. int r, y;
  13.  
  14. for( r = x; r != t[ x ]; r = t[x] );
  15.  
  16. while( x != t[ x ])
  17. {
  18. y = t[ x ];
  19. t[ x ] = r;
  20. x = y;
  21. }
  22. return r;
  23. }
  24.  
  25. void Unite( int x, int y )
  26. {
  27. if( c[ y ] <= c[ x ] )
  28. t[ y ] = x;
  29. else
  30. t[ x ] = y;
  31. if( c[ x ] == c[ y ] ) c[ x ] ++;
  32. }
  33.  
  34. int main()
  35. {
  36. cin >> n >> m >> q;
  37. for( int i = 1; i <= n; ++ i )
  38. {
  39. cin >> s;
  40. M[ s ] = i;
  41. Ant[ i ] = n + i;
  42. Ant[ n + i ] = i;
  43. t[ i ] = i;
  44. c[ i ] = 1;
  45. t[ n + i ] = n+i;
  46. c[ n + i ] = 1;
  47. }
  48. for( int i = 1; i <= m ; ++ i )
  49. {
  50. cin >> T;
  51. cin >> s1;
  52. cin >> s2;
  53. F1 = Find( M[ s1 ] );
  54. F2 = Find( M[ s2 ] );
  55. Fant2 = Find( Ant[ F2 ] );
  56. Fant1 = Find( Ant[ F1 ] );
  57. if( T == 1 )
  58. {
  59. if( F1 == Fant2 || F2 == Fant1 )
  60. {
  61. cout << "NO\n";
  62. continue;
  63. }
  64. Unite( F1, F2 );
  65. Unite( Fant1, Fant2 );
  66. cout << "YES\n";
  67. continue;
  68. }
  69. if( F1 == F2 )
  70. {
  71. cout << "NO\n";
  72. continue;
  73. }
  74. Unite( F1, Fant2 );
  75. Unite( Fant1, F2 );
  76. cout << "YES\n";
  77. }
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement