Advertisement
midnight_sun

Untitled

Nov 15th, 2022
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
  3. #define MAXN 1000001
  4. using namespace std;
  5. int n, m, parent[MAXN] = {}, lvl[MAXN] = {};
  6. int find(int u) {
  7.     if (u == parent[u]) return u;
  8.     return parent[u] = find(parent[u]);
  9. }
  10. void merge(int u, int v) {
  11.     u = find(u);
  12.     v = find(v);
  13.     if (u == v) return;
  14.     if (lvl[u] > lvl[u]) swap(u, v);
  15.     parent[u] = v;
  16.     if (lvl[u] == lvl[v]) lvl[v]++;
  17. }
  18. int main() {
  19.     fastio;
  20.     cin >> n >> m;
  21.     for (int i = 1; i <= n; i++) { parent[i] = i; lvl[i] = 1; }
  22.     for (int i = 0; i < m; i++) {
  23.         int c, a, b;
  24.         cin >> c >> a >> b;
  25.         if (c == 0) merge(a, b);
  26.         else {
  27.             a = find(a);
  28.             b = find(b);
  29.             if (a == b) cout << "YES\n";
  30.             else cout << "NO\n";
  31.         }
  32.     }
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement