典型タグ

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重みを求めるだけ
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

学習成果と学習単位

  • 同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。

    Kruskal順の閾値DSU sweepで学ぶ

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。