AIで解説 AtCoder攻略　Union-Find

Union-Findページの位置づけ

項目	内容
必修度	重要
学習目安	標準
前提	配列・木構造の見方
対象問題	31問（推定値あり31問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	0
標準	0〜799	10
標準〜発展	800〜1199	8
発展	1200以上	13
未算出	—	0

辺を追加・削除しながら、同じ連結成分かをほぼ定数時間で調べます。隣接リストを毎回たどる探索とは違い、連結性だけを親配列で管理する実装パターンです。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

Union-Findの見分け方

辺の追加と連結判定が何度も出てくる
成分の大きさや代表元だけが必要
距離や経路そのものは求めない

Union-Findの実装前チェック

findの経路圧縮とuniteのサイズ統合を用意する
0始まりの親配列と初期サイズをそろえる
距離を求める問題をUnion-Findで代用しない

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC284 C Count Connected Components（公式解説）を解きます。辺で結ばれた頂点をUnion-Findで同じ集合にまとめます。最後に各頂点の根を数えると、連結成分数になります。

N, M = map(int, input().split())
parent = list(range(N))
size = [1] * N

def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = find(a - 1), find(b - 1)
    if a != b:
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

print(len({find(i) for i in range(N)}))

経路圧縮とサイズ統合により、全体はほぼO((N+M)α(N))です。毎回DFSをやり直すより、辺を追加しながら管理できます。

Union-Findの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC284 C Count Connected Components	公式解説	Union every edge and count the remaining connected components.	108
ABC399 C Make it Forest	公式解説	Use DSU to detect cycle edges; removing one redundant edge per cycle makes each component a tree.	312
ABC304 C Virus	公式解説	Union people within distance D of an infected person and test connectivity.	365
ABC325 C Sensors	公式解説	Flood-fill 8-neighbor sensor cells to count connected components.	400
ABC288 C Don’t be cycle	公式解説	辺を追加し、既に同じ連結成分なら閉路を作る辺として数える。	436

次に解く

問題	公式解説	出題意図	difficulty
ABC277 C Ladder Takahashi	公式解説	Union ladder endpoints and output the largest reachable vertex in the component of 1.	540
ABC435 D G. Reachability Query 2	公式解説	公式Editorialの方針を reachability query dsu として整理する。	568
ABC177 D Friends	公式解説	友達関係の連結成分をUnion-Findで管理し、最大グループ人数を求める。	732
ABC350 D G. New Friends	公式解説	Official editorial intent is classified as dsu missing edges.	773
ABC462 D Accomplice	公式解説	Merge accomplice relations and inspect the resulting components.	798

挑戦問題

問題	公式解説	出題意図	difficulty
ABC293 D G. Tying Rope	公式解説	端点を結ぶロープをDSUで連結し、各成分が閉路か開鎖かを分類する。	830
ABC320 D G. Relative Position	公式解説	Propagate coordinate differences through a graph and answer relative positions.	873
ABC206 D KAIBUNsyo	公式解説	Union values that must become equal in mirrored positions and count one change per component beyond its majority value.	879
ABC304 E H. Good Graph	公式解説	Find DSU components and reject a restricted pair in one component.	971
ABC229 E H. Graph Destruction	公式解説	頂点削除を逆順の頂点追加に変換し、DSUで連結成分数を更新して各時点の答えを復元する。	1015