Advertisement
Josif_tepe

Untitled

Dec 18th, 2022
934
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <iostream>
  2.  
  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(idx[x] != x) {
  9.         idx[x] = idx[idx[x]];
  10.         x = idx[x];
  11.     }
  12.     return x;
  13. }
  14. bool find(int A, int B) {
  15.     if(find_root(A) == find_root(B)) {
  16.         return true;
  17.     }
  18.     return false;
  19. }
  20. void union_two_elements(int A, int B) {
  21.     int idx_A = find_root(A);
  22.     int idx_B = find_root(B);
  23.     if(size[idx_A] < size[idx_B]) {
  24.         idx[idx_A] = idx[idx_B];
  25.         size[idx_B] += size[idx_A];
  26.     }
  27.     else {
  28.         idx[idx_B] = idx[idx_A];
  29.         size[idx_A] += size[idx_B];
  30.     }
  31. }
  32. int main() {
  33.     for(int i = 0; i < maxn; i++) {
  34.         idx[i] = i;
  35.         size[i] = 1;
  36.     }
  37.     while(true) {
  38.         string s;
  39.         cin >> s;
  40.         if(s == "u") {
  41.             int a, b;
  42.             cin >> a >> b;
  43.             union_two_elements(a, b);
  44.         }
  45.         else {
  46.             int a, b;
  47.             cin >> a >> b;
  48.             if(find(a, b)) {
  49.                 cout << "YES\n";
  50.             }
  51.             else {
  52.                 cout << "NO\n";
  53.             }
  54.         }
  55.     }
  56.     return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement