完全永続 Union-Find
各頂点の親(根なら集合の大きさに $-1$ を掛けた値)を並べた配列を、 永続配列 と同じ考え方で持ちます。配列を二分木で表し、書き換えるときは根からその要素までの道のノードだけを複製するので、書き換える前の版もそのまま残ります。このファイルに永続配列(_get と _set)も入れてあるので、これだけで動きます。
経路圧縮をせず union by size だけを行うので、根にたどり着くまでに配列を読むのは $O(\log N)$ 回で、1 回読むのに $O(\log N)$ かかります。
版は番号で表し、初期状態が版 $0$ です。unite で新しい版ができるたびに、1 から順に番号を振ります。
PersistentUnionFind(n): $n$ 頂点で初期化。何もつないでいない状態が版 $0$。 $O(\log N)$(初めはすべての要素が同じなので、木の各段のノードを 1 つにまとめられる)unite(ver, a, b): 版 $\mathrm{ver}$ で $a$ と $b$ をつないだ新しい版の番号を返す。版 $\mathrm{ver}$ は変わらない。すでに同じ集合なら新しい版は作らず、verをそのまま返す(なので、返り値がverと等しいかで、つないだかがわかる)。 $O(\log^2 N)$ で、メモリが $O(\log N)$ 増えるfind(ver, x): 版 $\mathrm{ver}$ での $x$ の根。 $O(\log^2 N)$same(ver, a, b): 版 $\mathrm{ver}$ で $a$ と $b$ が同じ集合にあるか。 $O(\log^2 N)$size(ver, x): 版 $\mathrm{ver}$ での $x$ を含む集合の大きさ。 $O(\log^2 N)$
クエリをすべて先読みできる問題なら、版を頂点、unite を辺とする木(版の木)を作って根から DFS し、辺を下るときにつなぎ、戻るときに取り消すようにすると、 ロールバック付き Union-Find で同じことができます。そちらの方が速く、メモリも少なくて済みます。
例:
uf = PersistentUnionFind(4)
v1 = uf.unite(0, 0, 1) # 版 0 で 0 と 1 をつなぐ
v2 = uf.unite(v1, 2, 3) # 版 v1 で 2 と 3 をつなぐ
v3 = uf.unite(v1, 1, 2) # 版 v1 から枝分かれして 1 と 2 をつなぐ
print(uf.same(v2, 0, 3), uf.same(v3, 0, 2), uf.same(v3, 2, 3)) # False True False
print(uf.size(v2, 2), uf.size(v3, 0), uf.size(0, 0)) # 2 3 1
print(uf.unite(v3, 0, 2) == v3) # True(すでに連結なので版は変わらない)
# i 番目のクエリ (k, a, b): ver[k] の版で a と b をつないだものを ver[i] とする(ver[0] は初期状態)
uf = PersistentUnionFind(n)
ver = [0] * (len(queries) + 1)
for i, (k, a, b) in enumerate(queries, 1):
ver[i] = uf.unite(ver[k], a, b)
コード
class PersistentUnionFind:
# 初期状態が版 0。unite は元の版を残したまま、新しい版の番号を返す
# 各頂点の親(根なら -大きさ)を永続配列で持つ(union by size で経路圧縮はしない)
def __init__(self, n):
# 永続配列: 長さ 2^h の完全二分木。ノード o の子は C[o], C[o + 1](最下段では値)
h = 1
while (1 << h) < n:
h += 1
self.h = h
C = [-1, -1]
for _ in range(h - 1):
C += [len(C) - 2] * 2 # 初めはすべて -1 なので、各段のノードは 1 つを共有する
self.C = C
self.roots = [len(C) - 2] # roots[ver] = 版 ver の配列の根
def _get(self, o, i):
# 根が o の配列の i 番目
C = self.C
s = self.h - 1
while s:
o = C[o + (i >> s & 1)]
s -= 1
return C[o + (i & 1)]
def _set(self, o, i, x):
# 根が o の配列の i 番目を x にした配列の根を返す(i までの道のノードだけ複製する)
C = self.C
root = len(C)
C.append(C[o])
C.append(C[o + 1])
o = root
s = self.h - 1
while s:
k = o + (i >> s & 1)
c = C[k]
o = len(C)
C[k] = o
C.append(C[c])
C.append(C[c + 1])
s -= 1
C[o + (i & 1)] = x
return root
def find(self, ver, x):
# 版 ver での x の根
o = self.roots[ver]
p = self._get(o, x)
while p >= 0:
x = p
p = self._get(o, x)
return x
def unite(self, ver, a, b):
# 版 ver で a と b をつないだ新しい版の番号を返す(すでに同じ集合なら ver をそのまま返す)
a = self.find(ver, a)
b = self.find(ver, b)
if a == b:
return ver
o = self.roots[ver]
sa = self._get(o, a)
sb = self._get(o, b)
if sa > sb:
a, b = b, a
o = self._set(o, a, sa + sb)
o = self._set(o, b, a)
self.roots.append(o)
return len(self.roots) - 1
def same(self, ver, a, b):
# 版 ver で a と b が同じ集合にあるか
return self.find(ver, a) == self.find(ver, b)
def size(self, ver, x):
# 版 ver での x を含む集合の大きさ
return -self._get(self.roots[ver], self.find(ver, x))