Advertisement
Josif_tepe

Untitled

Oct 24th, 2023
796
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 1e5 + 10;
  6. const int INF = 1e9;
  7. int root[maxn];
  8. int sz[maxn];
  9. int find_root(int x) {
  10.     while(root[x] != x) {
  11.         root[x] = root[root[x]];
  12.         x = root[x];
  13.     }
  14.     return x;
  15. }
  16. bool check(int A, int B) {
  17.     int root_A = find_root(A);
  18.     int root_B = find_root(B);
  19.     return root_A == root_B;
  20. }
  21. void unite(int A, int B) {
  22.     int root_A = find_root(A);
  23.     int root_B = find_root(B);
  24.     if(root_A != root_B) {
  25.         if(sz[root_A] > sz[root_B]) {
  26.             root[root_B] = root[root_A];
  27.             sz[root_A] += sz[root_B];
  28.         }
  29.         else {
  30.             root[root_A] = root[root_B];
  31.             sz[root_B] += sz[root_A];
  32.         }
  33.     }
  34.    
  35.    
  36. }
  37. int main() {
  38.     for(int i = 0; i < maxn; i++) {
  39.         root[i] = i;
  40.         sz[i] = 1;
  41.     }
  42.    
  43.     while(true) {
  44.         string s;
  45.         cin >> s;
  46.        
  47.         if(s == "union") {
  48.             int a, b;
  49.             cin >> a >> b;
  50.             unite(a, b);
  51.         }
  52.         else {
  53.             int a, b;
  54.             cin >> a >> b;
  55.            
  56.             if(check(a, b)) {
  57.                 cout << "YES" << endl;
  58.             }
  59.             else {
  60.                 cout << "NO" << endl;
  61.             }
  62.            
  63.         }
  64.     }
  65.     return 0;
  66. }
  67.  
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement