ds/DSU.h

• View this file on GitHub
• Last update: 2025-11-18 16:58:39+07:00

Verified with

• tests/Unionfind.test.cpp

Code

struct DSU {
  int n;
  vi p;
  DSU(int n) : n(n), p(n, -1) {}
  int merge(int a, int b) {
    int x = head(a), y = head(b);
    if (x == y) return x;
    if (-p[x] < -p[y]) swap(x, y);
    p[x] += p[y], p[y] = x;
    return x;
  }
  bool same(int a, int b) { return head(a) == head(b); }
  int head(int a) {
    if (p[a] < 0) return a;
    return p[a] = head(p[a]);
  }
  int size(int a) { return -p[head(a)]; }
};

#line 1 "ds/DSU.h"
struct DSU {
  int n;
  vi p;
  DSU(int n) : n(n), p(n, -1) {}
  int merge(int a, int b) {
    int x = head(a), y = head(b);
    if (x == y) return x;
    if (-p[x] < -p[y]) swap(x, y);
    p[x] += p[y], p[y] = x;
    return x;
  }
  bool same(int a, int b) { return head(a) == head(b); }
  int head(int a) {
    if (p[a] < 0) return a;
    return p[a] = head(p[a]);
  }
  int size(int a) { return -p[head(a)]; }
};

Back to top page