Mirbek

СНМ (Система непересекающихся множеств)

Jan 14th, 2022
1,166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2. СНМ (Система непересекающихся множеств)
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e6 + 5;
  10.  
  11. int n, q;
  12. int p[N];
  13. int sz[N];
  14.  
  15. int find_set(int a) {
  16.     if (p[a] == a) return a;
  17.     p[a] = find_set(p[a]);
  18.     return p[a];
  19. }
  20.  
  21. void union_set(int a, int b) {
  22.     a = find_set(a);
  23.     b = find_set(b);
  24.     if (a == b) {
  25.         return;
  26.     }
  27.     if (sz[a] < sz[b]) {
  28.         p[b] = a;
  29.         sz[b] = sz[b] + sz[a];
  30.     } else {
  31.         p[a] = b;
  32.         sz[a] = sz[a] + sz[b];
  33.     }
  34. }
  35.  
  36. int main(){
  37.     cin >> n >> q;
  38.  
  39.     for (int i = 1; i <= n; i++) {
  40.         p[i] = i;
  41.         sz[i] = 1;
  42.     }
  43.  
  44.     for (int i = 1; i <= q; i++) {
  45.         int type;
  46.         cin >> type;
  47.         if (type == 1) {
  48.             int u, v;
  49.             cin >> u >> v;
  50.             union_set(u, v);
  51.         }
  52.         if (type == 2) {
  53.             int a, b;
  54.             cin >> a >> b;
  55.             if (find_comp(a) == find_comp(b)) {
  56.                 cout << "YES\n";
  57.             } else {
  58.                 cout << "NO\n";
  59.             }
  60.         }
  61.     }
  62. }
  63.  
RAW Paste Data