0Pricing
Coding Interview Prep · レッスン

ランクによる Union と連結成分

木を平坦に保ち、グループ数を数えます

「ランクによる Union と連結成分」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

Unionは遅延させてもよい

通常の union は、一方のルートをもう一方の下につなぐだけです。注意せずに行うと、高くて遅い木ができるため、ルートをより賢く統合する方法が必要です。

大きな考え方

Union by rankでは、常に短い木を高い木の下に取り付けます。木を浅く保つことで、その後の find をすべて高速にできます。📏

rankの意味

rankは、木の高さの推定値です。単一ノードの下には深さがないため、各要素の rank は最初は0です。

rank = [0] * n

短い木を高い木に付ける

2つのルートの rank を比較します。rank が小さいほうのルートを子にすることで、統合後の木をできるだけ平らに保ちます。

if rank[ra] < rank[rb]:
    parent[ra] = rb

同じrankならrankを上げる

両方のルートのrank が等しい場合は、どちらかを新しいルートにして、その rank を1増やします。木が1段高くなったためです。

else:
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Union by sizeという方法

よく使われる別の方法がunion by sizeです。小さい集合を大きい集合の下に付けます。同じくらい効果的で、集合のサイズもそのまま取得できます。

連結成分を数える

すべての要素が最初は単独の集合なので、countを n で始めます。union が成功するたびに2つの集合が1つになるため、値を1減らします。

components = n

何も変わらないunionを省く

2つの要素がすでに同じルートを共有している場合、union は何もしません。ルートが実際に異なる場合だけcountを減らします。

if find(a) != find(b):
    union(a, b)
    components -= 1

RankとCompressionの組み合わせ

union by rankとpath compressionを組み合わせると、DSUは逆アッカーマン時間で動作します。これは実際のどのような入力でも、実質的に定数時間です。⚡

必要なときに集合サイズを取得する

union by size を使えば、どの集合のサイズもすぐに答えられます。その要素のルートに保存されているsizeを読み取るだけです。

group = size[find(x)]

どのような場面で役立つか

コンポーネント数のカウントを使うと、union 操作を繰り返した後の友人グループの数や連結領域の数といった、典型的な問題に答えられます。🌐

確認問題

コンポーネント数がどのように変化するかを考えてみましょう。

振り返り

木を平坦に保つランクによる unionと、コンポーネント数やグループのサイズを追跡する方法を学びました。これで DSU は驚くほど高速です！🎉

よくある質問

「ランクによる Union と連結成分」レッスンは無料ですか？

はい。「ランクによる Union と連結成分」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「ランクによる Union と連結成分」で何を学びますか？

木を平坦に保ち、グループ数を数えます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「ランクによる Union と連結成分」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 経路圧縮付き DSU
  2. ランクによる Union と連結成分
  3. Kruskal の最小全域木
  4. ヒープを使う Prim の MST
← Coding Interview Prepに戻る