union_find.cpp

#include <numeric>
#include <vector>


using namespace std;

// Disjoint Set Union (Union-Find)
struct DSU {
  vector<int> parent;
  vector<int> size; // 그룹 크기 추적

  DSU(int n) {
    parent.resize(n + 1);
    iota(parent.begin(), parent.end(), 0); // 0, 1, 2, ...
    size.assign(n + 1, 1);
  }

  int find(int x) {
    if (parent[x] == x)
      return x;
    return parent[x] = find(parent[x]); // 경로 압축
  }

  bool unite(int a, int b) {
    a = find(a);
    b = find(b);

    if (a == b)
      return false;

    // Union by Size (더 큰 쪽으로 합치기)
    if (size[a] < size[b])
      swap(a, b);
    parent[b] = a;
    size[a] += size[b];
    return true;
  }

  bool same(int a, int b) { return find(a) == find(b); }

  int getSize(int x) { return size[find(x)]; }
};