概要
概要
Disjoint Set Union とも呼ばれます。連結成分の管理や Kruskal 法で重要な役割を持ちます。
データ構造 / Union-Find（ユニオンファインド）
Disjoint Set Union とも呼ばれます。連結成分の管理や Kruskal 法で重要な役割を持ちます。
目次
このページでわかること
概要
Disjoint Set Union とも呼ばれます。連結成分の管理や Kruskal 法で重要な役割を持ちます。
考え方
find(x)
find(y)
if roots differ then union them要点
ほぼ O(1) amortized
ほぼ O(1) amortized
path compression
連結判定
補足
同じグループかどうかを速く判定できます。
経路圧縮と union by rank によって木が浅く保たれるからです。
Kruskal 法の理解に直結します。
動きで確認
ここでは「何が制約か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。