Union-Find（素集合データ構造）
互いに素な集合の効率的な管理。パス圧縮とランク合併による最適化で実用的に定数時間を実現
O(α(n))
Find・Union
O(1)
実用的な操作時間
中級
難易度
O(n)
空間計算量
🌳 Union-Find操作設定
操作:
Union-Findの初期化
🎯 素集合の効率的な管理
📚 推奨操作例
🌳
Union-Find操作を実行してください
左側の入力パネルから操作を設定し、「Union-Find操作実行」ボタンを押してください
🎯 Union-Findの特徴と応用
最適化技法
- • パス圧縮（Path Compression）
- • ランクによる合併（Union by Rank）
- • 逆アッカーマン関数α(n)時間
- • 実用的に定数時間操作
実用的応用
- • グラフの連結性判定
- • クラスカル法（最小全域木）
- • 画像の連結成分ラベリング
- • ネットワーク分析
💡 学習ポイント: Union-Findは理論的に最適なオンラインアルゴリズムで、 実用的にほぼ定数時間での集合管理を実現します。