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 / よくある落とし穴
2 つの最適化を省く。
経路圧縮も union-by-size/rank も無い DSU は、最悪ケース(左偏チェーン)で操作あたり
O(N) に劣化する。いずれか一方で O(log N)、両方で α(N)。常に両方を入れること — どちらにしてもコードは 10 行ほど。比較前に find を忘れる。
「a と b は連結?」を見るには
find(a) == find(b) を比較する必要がある。parent[a] == parent[b] ではない。後者は直接の親しか見ない — 全体を平坦化した後でしか正しくならない。反復中に変更する。
経路圧縮は
find の中で parent 配列を書き換える。parent を直接走査しながら各要素に find を呼べば、 途中の半端な状態を見てしまう。先にスナップショットを取るか、 本当に最新の根が必要なときだけ find を呼ぶこと。05 / LeetCode で練習
中級20
01Longest Consecutive Sequence— LC 128→02Surrounded Regions— LC 130→03Number of Islands— LC 200→04Graph Valid Tree— LC 261→05Number of Connected Components in an Undirected Graph— LC 323→06Evaluate Division— LC 399→07Number of Provinces— LC 547→08Redundant Connection— LC 684→09Accounts Merge— LC 721→10Sentence Similarity II— LC 737→11Most Stones Removed with Same Row or Column— LC 947→12Satisfiability of Equality Equations— LC 990→13The Earliest Moment When Everyone Become Friends— LC 1101→14Connecting Cities With Minimum Cost— LC 1135→15Smallest String With Swaps— LC 1202→16Number of Operations to Make Network Connected— LC 1319→17Detect Cycles in 2D Grid— LC 1559→18Min Cost to Connect All Points— LC 1584→19Path With Minimum Effort— LC 1631→20Minimize Hamming Distance After Swap Operations— LC 1722→
難しい11
01Number of Islands II— LC 305→02Redundant Connection II— LC 685→03Couples Holding Hands— LC 765→04Swim in Rising Water— LC 778→05Bricks Falling When Hit— LC 803→06Minimize Malware Spread— LC 924→07Largest Component Size by Common Factor— LC 952→08Optimize Water Distribution in a Village— LC 1168→09Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree— LC 1489→10Rank Transform of a Matrix— LC 1632→11Checking Existence of Edge Length Limited Paths— LC 1697→