重みつき unionfind

重み付き unionfind で何ができるか.

任意の 2 つの要素で, どちらがどれだけ大きいかという情報を持つことができる.

以下の問題文を参考に.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp

まず, 重みなし unionfind とコードを比べてみよう

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; }
};

unionfind - tac_12のブログ より

struct WeightedUnionFind {
  vector<int> data;
  vector<ll> ws;
  int n;
  WeightedUnionFind(int n) : data(n, -1), ws(n) { }
  bool connect(int x, int y, ll w) {
    w += weight(x); w -= weight(y);
    if ((x = root(x)) == (y = root(y))) return false;
    if (data[x] > data[y]) swap(x, y), w = -w;
    data[x] += data[y]; data[y] = x; ws[y] = w;
    return true;
  }
  bool issame(int x, int y) { return root(x) == root(y); }
  int root(int k) {
    if (data[k] < 0) return k;
    int par = root(data[k]);
    ws[k] += ws[data[k]];
    return data[k] = par;
  }
  int size(int x) { return -data[root(x)]; }
  int size() { return n; }
  ll diff(int x, int y) { return weight(y) - weight(x); }
  ll weight(int t) { root(t); return ws[t]; }
};

一方の頂点の数の大きさが他方の頂点の数の大きさよりどれだけ大きいかで, 「数の大きさ」を重みと呼ぶ.

diff(int x, int y) は, 頂点 y の重み - 頂点 x の重みを返す.

root(int k) では, 根に近い方から再帰的に根の頂点番号をもらうわけだが, 同時にその頂点の重みを求める.
根は, その頂点番号を返すだけなので, 重みは変わらない.
根の重みは常に 0 である.

ある 2 頂点の重みの差を求めるとき, 根に対する相対的な重みを利用する.

根以外の頂点で, どう重みを持ち, どう重みを計算するのか.
connect では引数で, 頂点 y の重みが頂点 x の重みよりどれだけ大きいかが与えられる.
すなわち, ある 2 頂点の重みの差である.
頂点の重みは, 根からの相対的な重みであり, 根の重みは 0 なので, 根が根でなくなるタイミングを除いて root の ws[k] += ws[data[k]] は非 0 を足されない.
根が根でなくなるタイミングについては後に考える.

重みなし unionfind において, 各頂点常に正しい根の情報を持っているとは限らず, root を呼ばれたタイミングで正しい根を持つように, weight を呼ばれたタイミングで root を呼び, 正しい根と重みの情報を得る.

connect について説明する.
重みなし unionfind と同じく, x の集合の根は根のまま.
ここで, y の集合の根が根でなくなる.
x の集合の重みは基準の x の根の重みが 0 のままなので変わらないが, y の集合の重みは全体を変える必要がある.
満たされるべき条件は, connect の引数で与えられる.
すなわち, 2 集合の, 根とは限らない頂点 x, y に関して, x の重み + w = y の重み.
ここで, x の集合と y の集合の繋がり方であるが, x の集合の根に y の集合の根が繋がる.
y の集合の根の重みは 0 からどう変わるか.
結論から言うと, w + x の重み - y の重みである.
root(y) で y の重みを計算したら, x の重み + w になっていたらいい.
root を見ると, 根の情報が更新される前に根の重みが足される.
更新される前の根の重みは w + x の重み - y の重みになったのであった.
よって, y の重み + (w + x の重み - y の重み) = x の重み + w.
結局, y の集合全頂点の重みが w + x の重み - y の重みされているので, y の集合内での相対的な重みは変わっていない.

参考
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3810883#1