DSUによる連結成分管理・縮約
辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。
この典型を扱う単元: DSUによる連結成分管理・縮約
検索別名: DSU、Union-Find、disjoint set union、素集合データ構造
未知問からこの典型を見つける手掛かり
- 扱う対象
- 代表元
- 無向graph
- 連結成分
- 使う手掛かり
- component merge
- 同値
- 辺追加
- 保つ不変量
- component metadata
- root
- 求めるもの
- 成分縮約
- 連結判定
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 単調境界探索: 閾値以下の辺だけを有効化する単調判定器をDSUで共有するときに併用する。
- 最小・最大全域木とcut・cycle性質: Kruskal順に採用済み成分を管理する実装ではDSUを併用するが、cut・cycle性質そのものとは分けて学ぶ。
学習成果と学習単位
成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。
DSUによる連結成分管理・縮約で学ぶ静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。
DSUによる連結成分管理・縮約で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC235 E「MST + 1」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
- ABC408 E「Minimum OR Path」 公式問題主題: bitwise greedyによるmask最適化 / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 E「Destruction」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
- ABC229 E「Graph Destruction」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC233 F「Swap and Sort」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC235 E「MST + 1」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
- ABC238 E「Range Sums」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC239 F「Construct Highway」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC250 Ex「Trespassing Takahashi」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC264 E「Blackout 2」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC270 F「Transportation」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
- ABC276 E「Round Trip」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC279 F「BOX」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC286 G「Unique Walk」 公式問題主題: Euler trail・circuit / 補助タグ
- ABC295 G「Minimum Reachable City」 公式問題主題: 単調path contraction・DSU jump / 補助タグ
技能・出典
主題: 単調path contraction・DSU jump
主タグ: 単調path contraction・DSU jump / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約
- ABC301 Ex「Difference of Distance」 公式問題主題: lowlinkで橋・関節点を特定する / 補助タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、lowlinkによる橋・関節点の検出 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC302 Ex「Ball Collector」 公式問題主題: rollback・DFS入退場の状態復元 / 補助タグ
- ABC304 E「Good Graph」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC311 G「One More Grid Task」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC314 F「A Certain Game」 公式問題主題: DSU merge tree・Kruskal reconstruction tree / 補助タグ
- ABC328 E「Modulo MST」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC335 E「Non-Decreasing Colorful Path」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC349 G「Palindrome Construction」 公式問題主題: 回文半径と左右対称区間を特定する / 補助タグ
- ABC352 E「Clique Connect」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
- ABC355 F「MST Query」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
- ABC364 F「Range Connect MST」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
技能・出典
主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約、ordered set・multisetの動的順序管理
- ABC372 E「K-th Largest Connected Components」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC376 G「Treasure Hunting」 公式問題主題: 01 on Tree・親先行順序のcluster縮約 / 補助タグ
- ABC383 E「Sum of Max Matching」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
- ABC392 E「Cables and Servers」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC394 G「Dense Buildings」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC401 E「Reachable Set」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC408 E「Minimum OR Path」 公式問題主題: bitwise greedyによるmask最適化 / 補助タグ
- ABC409 F「Connecting Points」 公式問題主題: priority queue・best-first列挙 / 補助タグ
技能・出典
主題: priority queue・best-first列挙
主タグ: priority queue・best-first列挙 / 補助タグ: 有界全列挙・有限case分解、DSUによる連結成分管理・縮約
- ABC413 G「Big Banned Grid」 公式問題主題: 平面graph双対・cut/path対応 / 補助タグ
- ABC420 E「Reachability Query」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC434 E「Distribute Bunnies」 公式問題主題: DSUによる連結成分管理・縮約 / 主タグ
- ABC440 G「Haunted House」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC447 E「Divide Graph」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC451 F「Make Bipartite 3」 公式問題主題: 二部彩色と成分構造を扱う / 補助タグ