unionfind

前提知識
構造体, dfs

struct UnionFind {
  vector<int> data;
  int n;
  UnionFind(int n) : data(n, -1), n(n) {}
  bool connect(int x, int y) {
      if ((x = root(x)) == (y = root(y))) return false;
      if (data[x] > data[y]) swap(x, y);
      data[x] += data[y]; data[y] = x; n--;
      return true;
  }
  bool issame(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  int size() { return n; }
};

size() では, n を返す.
n は, 集合の個数.
最初, 頂点数.
どれも connect されていないので, すべてが大きさ 1 の集合.

size(int x) では, 頂点 x を含む集合の大きさを返す.
data[root(x)] = data[x を含む集合のグラフの根].
実は, data[根] は, その根を含む集合の大きさの負の数である.
例として, 最初, すべての頂点が大きさ 1 の集合で, 任意の頂点 v に対し, data[v] = -1.

各頂点の根は, root(int x) を呼び出されるタイミングで求める.
data[x] < 0 になるまで, 再帰的に root を呼ぶ.
根が呼ばれたら, 頂点番号 x を返すだけ.
根の data には, 根を含む集合のサイズの負の数が入っているが, これには触れられない.
根に近い方から, 根の頂点番号をもらい, 伝搬させていく.
再帰的に呼ばれた頂点の親は根に変えられ, 深さ 1 になっている.

コンストラクタの UnionFind(int n) : ... についても触れておく.
n が与えられて, data を, サイズが n で, すべてを -1 で初期化する.
また, UnionFind 内の変数 n に, 与えられた n を代入する.
書き方の問題だが, 別に UnionFind(int n) : n(n) { data = vector(n, -1); } でもいい.
UnionFind(int n) { n = n; data = vector(n, -1); } はダメ.

issame は, x, y 各々根を求めて同じか, すなわち, x, y が同じ集合の頂点か調べる.

connect を見る.
x, y 各々根を求めて, 同じなら既に同じ集合.
違う集合の頂点なら, 繋げる.
どう繋げるか.
頂点数が小さい方の根を, 頂点数が大きい方の根に繋げる.
x, y は根になっているとして, x の集合のサイズが 4, y の集合のサイズが 3 とする.
data[x] = -4 < -3 = data[y] より, swap しない.
x の集合に y の集合を繋げる.
data[x] = -4 - 3 = -7.
data[y] = x で, y の親が x になった.
n-- とあるが, n は集合の個数で, y の集合が x の集合に合併されたので, 1 減った.

複雑な例を図示しようとしたが, 頻繁に root が呼ばれるので, 大抵深さ 1 になる.