IxS7Oz - Online IDE & Debugging Tool

#include <bits/stdc++.h>
using namespace std;

int n, q;
const int N = 1e5 + 5;
int parent[N], sz[N];

void make_set(){
      // Đặt nút "cha" của mỗi tập hợp là chính nó
      // Tuy nhiên, ở đây ta đặt kích cỡ của tập hợp là chính nó, do đề bài yêu cầu tính tổng các đỉnh thành phần
      for (int i = 1; i <= n; i++){
            parent[i] = i;
            sz[i] = i;
      }
}

int find(int x){
      // Ta sử dụng kĩ thuật nén đường đi để tối ưu
      if (parent[x] == x) return x;
      int p = find(parent[x]);
      parent[x] = p;
      return p;
}

void set_union(int a, int b){
      // Đặt nút "cha" của b là a
      a = find(a); b = find(b);
      if (a != b){
            /*
            Ở đây ta dùng swap để thuận tiện hơn
            Thay đổi kích cỡ của tập hợp a
            Đặt nút "cha" của b là a
            */
            if (sz[a] < sz[b]) swap(a, b);
            sz[a] += sz[b];
            parent[b] = a;
      }
}

void input(){
      cin >> n >> q;
      make_set();
      for (int i = 1; i <= q; i++){
            int t, u, v;
            cin >> t;

            if (t == 1){
                  // Nối 2 đỉnh u, v
                  cin >> u >> v;
                  set_union(u, v);
            }
            else{
                  // In ra tổng thành phần của đỉnh u
                  cin >> u;
                  cout << sz[find(u)] << endl;
            }
      }
}

int main(){
      input();

      return 0;
}