グラフ（応用）Unionfind, 最小全域木
| 問題 | 難易度 | 重要度 | テクニック |
|---|---|---|---|
| Disjoint Set | ★★★★ | 高 | UnionFind(UnionFindForest) |
| Redundant Connection | ★★★★ | 高 | UnionFind(UnionFindForest) |
| Weighted Union Find Trees | ★★★★★ | 低 | UnionFind(UnionFindForest) |
| Min Cost to Connect All Points | ★★★★ | 高 | Minimum Spanning Tree（最小全域木） |
| Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree | ★★★★★ | 中 | Minimum Spanning Tree（最小全域木） |
UnionFind(UnionFindForest)
UnionFind（またはUnionFindForest）はデータを*互いに素な集合に効率良く分類して管理するデータ構造です。UnionFindでは複数の木を使ってこれを実現します。この複数の木を森と呼ぶため、UnionFindForestとも呼ばれます。UnionFindは特に動的にグループの状況を知りたいときに非常に効果的になります。
互いに素な集合 1つのデータが1つのグループにしか所属しないことです。（複数のグループに所属しない。）
例題. Number of Island
難易度:★★★★ 重要度: 高
この続きは、購入者向けの内容です。
非表示コンテンツ 📝 18,319文字 🖼 8枚の画像
続きは購入後に閲覧できます。
この教材を購入 ↗