Advertisement
Josif_tepe

Untitled

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