Day 149-Q3 | Union-Find with Rollback

問題

N頂点のグラフに対し、次の3種のクエリがQ個順に与えられる。

1 u v: 頂点u,vを併合（union by size。既に同じ集合なら何もしない）
2 u v: 同じ集合か判定しYes/Noを出力
3 k: 直前のunion系クエリのうち最新k回分を取り消す（何もしなかった呼び出しも1回とカウント）

union by size: 代表元が異なる場合、集合サイズが小さい方を大きい方へ付け替える（同サイズならu側を優先して付け替え）。経路圧縮は行わない。

入力形式

N Q
query_1
:
query_Q

制約

$1 \le N \le 20$

$1 \le Q \le 50$

3 kのkはその時点までのunion回数以下

2 u vの$u,v$は$0$〜$N-1$

入出力例

入力例1

出力例1

Yes
No
No
No
No

3 2で直前2回のunion（1 3 4と1 1 2）を取り消し、{0,1}/{2}/{3}/{4}に戻る。

概念図：union履歴スタックとrollback

ヒント（段階的開示）

ヒント1（方向性）

経路圧縮ができない代わりに、unionのたびに「何を書き換えたか」を記録すれば、記録を逆順にたどって書き換えを元に戻せる。木の高さがunion by sizeだけで$O(\log N)$に保たれる。

ヒント2（アプローチ）

1回のunionで変化する状態は「小さい方の代表元の親ポインタ」と「大きい方の代表元のサイズ」の2箇所だけ。この2つを履歴に1エントリ保存すればrollbackで完全復元できる。何もしなかったunionもno-opとして履歴を消費させないと、kの数え方がずれる。

ヒント3（誘導）

def union(self, a, b):
    ra, rb = self.find(a), self.find(b)
    if ra == rb:
        self.history.append(None)
        return
    if self.size[ra] < self.size[rb]:
        ra, rb = rb, ra
    self.history.append((rb, ra, self.size[ra]))
    self.parent[rb] = ra
    self.size[ra] += self.size[rb]

模範解答 (Python)

import sys


class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.history = []

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            self.history.append(None)
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.history.append((rb, ra, self.size[ra]))
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]

    def rollback(self, k):
        for _ in range(k):
            rec = self.history.pop()
            if rec is None:
                continue
            rb, ra, old_size = rec
            self.parent[rb] = rb
            self.size[ra] = old_size

    def same(self, a, b):
        return self.find(a) == self.find(b)


def main():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx + 1]); idx += 2
    dsu = RollbackDSU(N)
    out = []
    for _ in range(Q):
        t = int(data[idx]); idx += 1
        if t == 1:
            u, v = int(data[idx]), int(data[idx + 1]); idx += 2
            dsu.union(u, v)
        elif t == 2:
            u, v = int(data[idx]), int(data[idx + 1]); idx += 2
            out.append("Yes" if dsu.same(u, v) else "No")
        else:
            k = int(data[idx]); idx += 1
            dsu.rollback(k)
    print('\n'.join(out))


main()

Step-by-Step 解説

1経路圧縮ができない理由
経路圧縮は探索経路上の全ノードの親を根に直結させ、木の形を不可逆的に変える。全変更を記録するのはコストが高くrollbackの旨味がなくなる。union by sizeのみで高さを$O(\log N)$に抑える。

21回のunionが変える箇所は2つ
小さい方の親ポインタと大きい方のサイズだけ。1回のunionごとに定数個の情報を保存すれば復元可能。

3no-opも履歴に積む理由
3 kは「直前k回のunionクエリ」を取り消す仕様であり、実際に変化した回数ではない。no-opも履歴のスロットを1つ消費させる必要がある。

4rollbackは履歴を逆順に戻すだけ
履歴は変更前の値を保存しているので、スタックから取り出した順にparentとsizeを書き戻せば正確に復元される。

よくあるミス

ミス	原因	正しい書き方
`find`に経路圧縮を入れてしまう	通常のUnion-Findの癖	rollback可能な構成では経路圧縮を絶対に入れない
no-opのunionを履歴に積まない	「何も変化しなかったから不要」と誤解	`None`マーカーを積み、rollback回数を合わせる
rollback時にsizeを戻し忘れる	parentだけ戻せば十分と誤解	併合先のsizeも保存し必ず元に戻す
同サイズ時の付け替え方向が不統一	判定を決めていない	本問では同サイズなら`u`側を大きい方とみなして統一
`k=0`のロールバックで特別処理	境界条件の考慮漏れ	`range(0)`は自然にループが回らないので不要

次のステップ

発展: 本構造は「辺の有効区間」をセグメント木に載せ、各ノードで辺をunionし葉に到達したらrollbackする「オフライン動的連結性」の基礎部品になる。
次回予告: LOUDS（Level-Order Unary Degree Sequence・簡潔木表現、Day145-Q3の簡潔ビットベクトルの続編）

自己評価

完全理解おおむね理解要復習

Day 149-Q3 — Union-Find with Rollback（ロールバック可能Union-Find・union by sizeのみで履歴管理）

問題