Kruskal順の閾値DSU sweep
辺とqueryを重み順に並べ、同重みの処理順を明示してDSU成分とmetadataを更新し、二点が初めて連結するminimax閾値で判定・pairing・集計を行う。
この典型を扱う単元: Kruskal順の閾値DSU sweep
検索別名: Kruskal順DSU sweep、minimax connectivity threshold、weight-sorted offline connectivity sweep、重み順Union-Find
未知問からこの典型を見つける手掛かり
- 扱う対象
- component metadata
- threshold components
- weighted undirected graph
- 使う手掛かり
- 成分併合時に需要を相殺
- 最初に連結する時刻
- 重みw未満または以下で連結
- 保つ不変量
- merge time is minimax distance
- processed edges equal the threshold subgraph
- 求めるもの
- MST採用可能性
- 最早可能なcomponent pairing
- 閾値別連結判定
- 適用しない条件
- 再構成木を明示して後からquery
- 単にMST重みを求めるだけ
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- DSUによる連結成分管理・縮約: 辺重み順に追加される閾値部分graphの連結成分をDSUで増分管理する。
- 最小・最大全域木とcut・cycle性質: Kruskalの辺順とcut性質を、MST構築だけでなく閾値部分graphの連結時刻・成分metadataの増分処理へ拡張する。
学習成果と学習単位
同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。
Kruskal順の閾値DSU sweepで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC235 E「MST + 1」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ
- ABC250 Ex「Trespassing Takahashi」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC301 Ex「Difference of Distance」 公式問題主題: lowlinkで橋・関節点を特定する / 主タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、lowlinkによる橋・関節点の検出 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC383 E「Sum of Max Matching」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC235 E「MST + 1」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ
- ABC250 Ex「Trespassing Takahashi」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC301 Ex「Difference of Distance」 公式問題主題: lowlinkで橋・関節点を特定する / 主タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、lowlinkによる橋・関節点の検出 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC383 E「Sum of Max Matching」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ