経路圧縮付き DSU
ほぼ定数時間で Find と Union を行います
「経路圧縮付き DSU」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
DSUが追跡するもの
Disjoint Set Unionは、要素を互いに重ならない集合にまとめます。そのため、2つの要素がすでに同じ集合に属しているかを確認できます。🤝
木としての集合
DSUは各集合を木として保存します。各要素はparentを指し、最上位のノードであるルートが集合全体を一意に表します。
parent 配列
これらのリンクをすべて1つの配列で管理します。最初は各要素自身をparentに設定し、すべての要素が単独の集合から始まるようにします。
parent = list(range(n))ルートを探す
find操作では、要素が自分自身を指すまで parent のリンクを上へたどります。その自分自身を指すノードが、集合を識別するルートです。
while parent[x] != x:
x = parent[x]長いチェーンは負担になる
何も工夫しないと、集合が細長いチェーンになることがあります。するとfindはノードを1つずつたどるため、1回のクエリに O(n) かかることがあり、非常に遅くなります。
Path Compressionの導入
Path compressionはこの問題を解決します。ルートを探す途中で、訪れたすべてのノードをルートへ直接つなぎ直し、次回に備えて木を平らにします。⚡
再帰による圧縮
最もわかりやすい方法は再帰です。ルートを探し、戻る前にそれをparent[x]へ保存します。これによりリンクが恒久的に短くなります。
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]2つの要素は同じ集合か
2つの要素が連結しているかを調べるには、ルートを比較します。find(a) と find(b) が等しいなら同じ集合に属し、異なるならまだ別々です。
if find(a) == find(b):
print("connected")2つの集合を統合する
union操作は、一方のルートをもう一方のルートにつなぐことで集合を統合します。1行で2つの木全体を1つの集合にできます。
def union(a, b):
parent[find(a)] = find(b)非常に高速な理由
圧縮だけでも、操作は償却計算量でおよそO(log n)で実行できます。さらにランク付けと組み合わせると、クエリあたりほぼ定数時間になります。
DSUが活躍する場面
DSUは連結性に関する問題で力を発揮します。友人関係のグループ、ネットワークの連結成分、Kruskal の全域木は、いずれも高速な find と union を利用します。🌐
クイックチェック
Path compression が実際に何を変えるのか考えてみましょう。
まとめ
DSUを作りました。parent 配列、ルートを取得する find、集合を統合する union です。Path compression によって非常に高速に動作します。よくできました！🎉
よくある質問
「経路圧縮付き DSU」レッスンは無料ですか？
はい。「経路圧縮付き DSU」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「経路圧縮付き DSU」で何を学びますか？
ほぼ定数時間で Find と Union を行います ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「経路圧縮付き DSU」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。