Union Find
01 / 一文での本質
N個の要素を互いに素な成分に分割し続け、 2 つの成分を 1 つに併合する操作をほぼ定数時間で行う。森のような構造で、根こそが その成分の代表であり、findはたどった経路を毎回短くする。
問題DSU で連結成分を数えるノード数6辺数5
開始:6 個のノード、それぞれが自分自身の成分。辺を 1 本ずつ処理 — 各 union が 2 つの木を合併する。
ステップ
0 / 16
辺
—
動作
初期化
成分数
6
0 / 16
02 / パターンの骨格
# 2 つの配列 + 2 つの操作parent[i] ← i # 最初は誰もが自分自身の根size[i] ← 1 def find(x):while parent[x] ≠ x:parent[x] ← parent[parent[x]] # 経路圧縮x ← parent[x]return x def union(a, b):ra, rb ← find(a), find(b)if ra == rb: return Falseif size[ra] < size[rb]: ra, rb ← rb, raparent[rb] ← ra # 小さい方を大きい方の下にsize[ra] += size[rb]return True
03 / このパターンを使うべき合図
「連結成分」
いくつかの要素が同じグループに属するかを数えたり問い合わせたりする。同値関係:反射的・対称的・推移的。 各ノードから素朴に BFS/DFS したくなったら、Union Find を疑え。
「2 つのグループの併合」
問題はクラスタを段階的に併合していく — 友人が友人の友人になる、辺が 1 本ずつ加わる、メールを共有するアカウント。併合の構造そのものは問わず、メンバーシップだけが重要。
「無向グラフの閉路検出」
辺を 1 本ずつ追加し、両端が既に同じ成分にあるなら、その辺が閉路を作る。 Kruskal の MST や LC 684 で使われる。
「オフラインクエリ」
クエリをバッチで処理できる(オンラインでない)場合、DSU は 「k 回の操作後に x と y は連結か?」をクエリあたりほぼ定数時間で答えられる。
04 / よくある落とし穴
i.
2 つの最適化を省く。
経路圧縮も union-by-size/rank も無い DSU は、最悪ケース(左偏チェーン)で操作あたり
O(N) に劣化する。いずれか一方で O(log N)、両方で α(N)。常に両方を入れること — どちらにしてもコードは 10 行ほど。ii.
比較前に find を忘れる。
「a と b は連結?」を見るには
find(a) == find(b) を比較する必要がある。parent[a] == parent[b] ではない。後者は直接の親しか見ない — 全体を平坦化した後でしか正しくならない。iii.
反復中に変更する。
経路圧縮は
find の中で parent 配列を書き換える。parent を直接走査しながら各要素に find を呼べば、 途中の半端な状態を見てしまう。先にスナップショットを取るか、 本当に最新の根が必要なときだけ find を呼ぶこと。05 / LeetCode で練習
ファミリーから 4 問。最初の 1 問は定番の「県の数」入門。 次の 2 問は構造を増やす(閉路検出、重み付き辺)。 4 問目はノードキーを文字列にする — 同じ DSU コアにハッシュマップを被せただけ。