コーディング面接：Union-Find の実装と連結成分の追跡方法

問題の要件と範囲

0 から n - 1 までのラベルが付けられた n 個のノードがあります。初期状態では、すべてのノードがそれぞれ独立した連結成分です。以下の操作を持つ UnionFind を実装してください：

• union(a, b)：a と b を含む成分を統合します。以前は別々だった2つの成分が実際に統合された場合にのみ True を返します。
• connected(a, b)：2つのノードが現在同じ成分に属しているかどうかを報告します。
• count()：現在の連結成分の数を返します。

このバージョンでは n = 0 が許可されますが、操作の引数は有効なラベルである必要があり、そうでない場合は IndexError を発生させます。 基本問題では接続の追加のみを行い、辺の削除は行わず、呼び出しは単一スレッドから行われます。 例えば、n = 6 から開始し、(0, 1)、(1, 2)、(3, 4) を統合すると、3つの 成分は {0, 1, 2}、{3, 4}、{5} になります。(2, 4) を統合すると成分は2つ残ります。その後の union(0, 3) は、カウントを再度減らすことなく False を返さなければなりません。

これは一般的なソフトウェアエンジニアリングのデータ構造に関する面接問題です。その中心的なユースケースは、 多くの連結性クエリや成分数クエリとインターリーブされた、接続の増分ストリームです。 すべての辺が一度に提供され、呼び出し側が1つの成分数のみを必要とする場合は、DFS や BFS の方が直接的であることが多く、 その違いを認識することが優れた回答の一部となります。

面接官が評価するポイント

最初の評価シグナルは状態の選択です。Union-Find は完全なグラフを保持しません。各集合を 親ポインタ木として表現し、その根が集合の代表となり自身を指します。その結果、 connected(a, b) は保存されたすべての辺を走査する代わりに2つの根を比較できます。

2番目のシグナルは、union が根同士のみを結合しているかどうかです。parent[a] = b を直接記述すると、 内部ノードが別のノードの下に移動し、元の成分の表現が破損する可能性があります。 正しい手順は、root_a と root_b を見つけ、それらが異なることを確認し、より小さい 木の根をより大きい木の根に取り付けます。size は根でのみ意味を持ち、木の成長を制御します。

3番目のシグナルは、単に暗記したテンプレートではなく、経路圧縮についての説明です。この 実装では経路半減法（path halving）を使用します。find が上にたどる際、現在のノードの親をその 祖父に変更します。その新しい親も同じ木の中にあるため、連結性は維持されたまま将来の 経路が短くなります。また、反復形式により、長い経路での再帰の深さ超過エラーを回避できます。

最後に、面接官はカウントの不変条件、計算量の用語、および検証を確認します。 components は n から始まり、異なる2つの根が統合された後にのみ減少します。重複した union や 自己 union によって変化することはありません。union by size と経路圧縮を組み合わせることで、一連の操作は ならしで O(α(n)) の時間を要します（すべての呼び出しに対する厳密な最悪計算量 O(1) ではありません）。

回答前の確認事項

• 接続は追加のみですか、それとも削除も可能ですか？ 標準の Union-Find は追加を処理します。

任意の辺が削除された後、親フォレストから他の辺がまだ端点同士を接続しているかどうかを判別することはできません。 それにはオフライン手法またはより高度な動的連結性データ構造が必要です。

• クエリはオンラインでインターリーブされていますか、それともすべての辺が事前に提供されますか？ union クエリと

連結性クエリがインターリーブされている場合は Union-Find が適しています。静的グラフでの1回の成分カウントには、 隣接リストによる DFS/BFS の方がわかりやすく、実際の辺も保持されます。

• union は何を返すべきですか？ ここでは統合が行われたかどうかを報告します。そのブール値はサイクル検出を

直接サポートし、成分数が正確に1回だけ変化することを保証します。

• 無効なノードはどのように振る舞うべきですか？ このバージョンでは IndexError を発生させます。競技プログラミングの

解法では有効性が保証された規約の下でバリデーションを省略できますが、公開実装では Python の負のインデックスが 暗黙的に配列の末尾を参照してはなりません。

• API は成分のサイズを報告したり、メンバーを列挙したりする必要がありますか？ 根の size を使用すれば、

ほぼ一定のならし時間でサイズを答えることができます。メンバーの列挙には少なくとも出力サイズ分のコストが依然としてかかり、 この基本構造ではメンバーシップリストを保持しません。

• 呼び出しは並行して行われる可能性がありますか？ 基本実装は find 内で parent を変更するため、

連結性クエリであっても読み取り専用ではなく、スレッドセーフでもありません。並行性を担保するには、ロック規約または 特殊な並行 Union-Find アルゴリズムが必要です。

30秒の回答フレームワーク

「長さ n の2つの配列を保持します。parent[x] は親を指し、size[root] は 根の木のサイズを格納します。初期状態では各ノードが自身の親であり、成分数は n です。find は 根までたどり、訪問した各ノードをその祖父に繋ぎ変えることで経路半減法を実行します。union は両方の 根を見つけます。それらが等しい場合は False を返します。等しくない場合は、小さい木の根を 大きい木の根に取り付け、それらのサイズを加算し、成分数をデクリメントして True を返します。2つの 根を結合してもサイクルは作成されず、経路半減法は1つの集合内のポインタのみを変更するため、 連結性は正しく保たれます。初期化は O(n)、その後の操作はならしで O(α(n))、 空間計算量は O(n) です。」

ステップごとの詳細解説

直接的な表現方法としては、すべてのノードに成分ラベルを割り当てることが考えられます。connected はラベルの比較になりますが、 2つの成分を統合するには配列全体を走査して古いラベルをすべて置き換える必要があり、 1回の union に O(n) のコストがかかります。もう1つの素朴なアプローチは親ポインタ木を使用することですが、 木のサイズを制御せずに根を取り付けます。この場合、敵対的な union の順序によって長い一本鎖が作られ、 find のパフォーマンスが低下する可能性があります。

推奨される設計では、次の3つの状態を維持します：

1. parent[x] は x の親であり、すべての木の根は parent[root] == root を満たします。
2. size[root] はその根の成分のノード数です。根以外のノードにある古い値が読み取られることはありません。
3. components は親フォレスト内の根の数と等しくなります。

実装は以下の通りです。_validate は短く、このクラスでのみ使用されるため、 個別のユーティリティモジュールにはせず、呼び出し箇所の近くに配置します。

class UnionFind:
    def __init__(self, n: int) -> None:
        if n < 0:
            raise ValueError("n must be non-negative")
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def _validate(self, x: int) -> None:
        if x < 0 or x >= len(self.parent):
            raise IndexError("node out of range")

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

    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False

        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def count(self) -> int:
        return self.components

正当性は3つのステップで導かれます。初期状態では、すべてのノードが1ノードからなる木の唯一の根であるため、 フォレストには n 個の木が存在し、3つの不変条件がすべて成立します。経路半減法は x の親を元の 親の親に変更します。その祖父は元の根への同じ経路上に残っているため、この操作によって 成分を越えてしまったり、find(x) が返す根が変わったりすることはありません。

union は2つの根のみを変更します。根が等しいことはノードがすでに連結していることを意味するため、状態は変化しません。 異なる根の場合、root_b を root_a に向けることで2つの木が1つに結合されますが、これらの根は 別々の木に属していたためサイクルが作成されることはありません。新しい根のサイズは元の木のサイズの合計になり、 根の数は正確に1つ減少します。数学的帰納法により、2つのノードが連結していることと find が 同じ根を返すことは同値であり、count() は常に真の成分数と一致します。

union by size により、ノードの深さがその木全体が取り付けられたことで増加するたびに、 その新しい成分のサイズは少なくとも2倍になることが保証されます。経路圧縮を行わなくても、木の高さは最大で O(log n) です。経路半減法と組み合わせると、初期化後の m 回の find および union の一連の操作の ならし上限は O(m α(n)) になります。逆アッカーマン関数 α の増加は極めて緩やかです。「ほぼ 一定のならし時間」は面接での正確な簡略表現ですが、「厳密な最悪計算量 O(1)」は誤りです。2つの 配列は O(n) の空間を使用し、反復形式の find は O(1) の補助スタック空間を使用します。

状態は以下の操作シーケンスで追跡できます：

n = 6                         count = 6
union(0, 1) -> True           count = 5
union(1, 2) -> True           count = 4
union(3, 4) -> True           count = 3
connected(0, 2) -> True
connected(0, 4) -> False
union(2, 4) -> True           count = 2
union(0, 3) -> False          count = 2

検証には複数のテストケースが必要です。クエリのない n = 0、n = 1 の自己 union、 重複した union、ブリッジで結ばれた2つの別々の成分、孤立ノード、逆順で提示された union、 そして無効なラベル -1 と n をカバーします。ランダムな小さなグラフに対しては、オラクルとして隣接リストを 保持します。辺を挿入するたびに BFS で連結性と成分数を再計算し、 Union-Find とステップごとに比較します。この差分テストにより、カウントや根に関する微妙なバグを検出できます。

すべての m 本の辺が事前にわかっており、呼び出し側が1つの成分数のみを求める場合、隣接リストによる DFS/BFS は O(n + m) の時間と空間を使用し、意図を明確に表現できます。Union-Find の真価が発揮されるのは、 辺が逐次的に到着し、クエリが union とインターリーブされる場合や、クラスカル法で 無向辺がサイクルを形成するかどうかをテストする必要がある場合です。単にグラフが存在するかどうかではなく、操作モデルに基づいて選択します。

質の高い模範解答

「まず、関係の追加のみが行われ、クエリが追加とインターリーブされ、 union が統合が発生したかどうかを報告する必要があることを確認します。その操作モデルには Union-Find が適しています。これが 静的グラフに対する1回の成分カウントであれば、代わりに DFS を使用します。

保持する状態は、parent、根における size、そして現在の根の数である components です。各ノードは 初期状態では自身を指します。find は反復処理で根に向かって進み、訪問した各ノードをその祖父に 向けることで、再帰を使わずに経路を短縮します。union は両方の根を取得します。根が等しい場合は False を返し、カウントは変更しません。そうでない場合は、小さい木の根が大きい木の根を指すようにし、 サイズを加算してカウントをデクリメントします。

この表現構造はフォレストを維持します。経路半減法はノードを同じ木内の祖先にのみ向け、 union は異なる2つの木の根同士を接続するため、どちらの操作も親のサイクルを作成しません。 union が成功するたびに正確に2つの木が1つになるため、カウントの不変条件も証明されます。

配列の構築には O(n) のコストがかかります。union by size と経路半減法により、find、connected、 union はならしで O(α(n))、空間計算量は O(n) です。テストでは、自己 union や重複 union で カウントが変化しないこと、2つの大きな成分の架橋、孤立ノード、空の構造、および 無効な負のラベルのテストを重視します。また、ランダムな小規模ケースに対して BFS との差分テストも行います。」

よくある間違い

• parent[a] = b を直接代入する → a が根ではない可能性があり、元の木が分割されたり

制御不能な一本鎖になったりします → 両方の根を見つけて、根同士のみを結合してください。

• 常に2番目の木を最初の木に取り付ける → 敵対的な順序によって長い経路が作成されます → **根の

size または rank を使用して方向を選択してください。**

• find から parent[x] のみを返す → 親が根であるとは限らないため、間接的な連結性が

誤判定されます → 自身を親とする根に達するまでポインタをたどってください。

• union の呼び出しごとに components をデクリメントする → 重複 union や自己 union によって

カウントが実際より少なくなります → 根が異なる場合にのみ更新してください。

• 根を入れ替えた後に古い根のサイズを更新する → メタデータが実際の木と乖離します →

まず最終的な親となる根を決定し、その後一貫性を持って結合およびサイズ加算を行ってください。

• 操作ごとに最悪計算量 O(1) であると主張する → 保証されるのは一連の操作に対するならし計算量であり、

逆アッカーマン関数を含みます → ならし計算量 O(α(n)) と報告してください。

• Python の負のインデックスを無視する → find(-1) が失敗せずに最後のノードにアクセスしてしまいます →

公開実装では両方の境界を検証してください。

• 任意の辺削除に基本的な Union-Find を使用する → 親ポインタは削除後の代替経路を

保持しません → オフラインでの削除処理、ロールバック付き Union-Find、または動的連結性データ構造を使用してください。

• connected を読み取り専用として扱う → 経路半減法は parent に書き込みを行うため、並行呼び出し下で

競合が発生します → グローバルロック、パーティショニング、または並行アルゴリズムを選択する前に、同期仕様を定義してください。

発展的な質問と対策

質問 1：Union-Find を使って無向グラフのサイクルを検出するにはどうすればよいですか？

辺 (u, v) を1本ずつ処理します。もし union(u, v) が False を返した場合、新しい辺を追加する前に 両端点がすでに連結していたことになるため、その辺によってサイクルが閉じられます。True という結果は、 以前は別々だった2つの成分を結合したことだけを示します。このルールは無向グラフに直接適用できます。有向グラフのサイクル検出には、 3色 DFS やトポロジカルソートなどの手法が必要です。

質問 2：直前の union を元に戻す（Undo）必要がある場合はどうしますか？

ロールバック付き Union-Find を使用します。union by size を維持し、実際の変更を行う前に、変更前の親、根のサイズ、 成分数を履歴スタックに push します。Undo はそれらの値を復元します。1回の find が 多数のエントリを変更し、ロールバックログを肥大化させ境界の処理を複雑にするため、通常は経路圧縮を省略します。 union by size 単独でも木の高さは O(log n) に抑えられ、オフラインの操作タイムラインに対する 分割統治法と非常にうまく機能します。

質問 3：関係を任意に削除できる場合はどうなりますか？

標準の Union-Find では任意のオンライン削除に対応できません。操作シーケンス全体が既知の場合は、 各辺のアクティブな時間区間を時間軸上のセグメント木に配置し、ロールバック付き Union-Find で それを走査します。末尾でのみ発生する削除は、逆順にして追加操作として処理することもできます。真に オンラインで頻繁な挿入、削除、クエリには、より高度な完全動的連結性データ構造が必要です。 したがって、操作がオフラインかどうかは問題を定義づける重要な確認事項です。

質問 4：ある成分のサイズや、そのすべてのメンバーを返すにはどうすればよいですか？

サイズはすでに根に格納されているため、size_of(x) = size[find(x)] は同じならし計算量を維持します。 メンバーの一覧は、根のサイズだけから復元することはできません。すべてのノードを走査して根を比較すると O(n α(n)) のコストがかかります。メンバーの集合を保持すると、マージとメモリのコストが増加します。 たまに出力する程度であれば、走査する方が通常はシンプルです。頻繁に列挙する場合は、別の表現方法を検討する価値があります。

質問 5：複数のスレッドからの呼び出しをどのように処理しますか？

最も小さく正確な変更は、find、union、および connected を1つのミューテックスで保護することです。 経路半減法が親配列への書き込みを行うためです。これは正当性の証明が容易ですが、すべての操作が直列化されます。 計測された競合が存在して初めて、アトミックな compare-and-swap、決定論的リンク、または パーティショニングに基づく並行設計が正当化されます。そのような設計では、非巡回な親ポインタとアトミックな サイズおよび成分数の更新を再証明する必要があります。単に配列をアトミック変数に置き換えるだけでは不十分です。