ABC 302 E — Isolation

考察

各query後に必要なのは孤立頂点数だけである。辺追加で変化するのは両端、頂点vの全辺削除で変化するのはvとその隣接頂点だけなので、全頂点を数え直す必要はない。

採用する候補: 頂点ごとの隣接集合と孤立頂点数を動的に保つ

棄却する候補: 各query後に全頂点の次数を走査する

1回O(N)となり、Q回のqueryに対して制約を超える。

初期値を孤立頂点数Nとする。辺(u,v)追加時は追加前の隣接集合が空なら各端点について1減らして相互に挿入する。全辺削除時はvの各隣接uからvを消し、uが空になれば1増やし、最後にvを空にして必要なら1増やす。

典型の発動条件

動的グラフの隣接集合

発動条件: 辺の追加と、指定頂点に接続する全辺の削除が混在する。

各頂点の隣接先をsetで持ち、追加・削除と次数0判定を同じ表現で行う。

償却計算量

発動条件: 一つの更新が多数の辺を消すが、消した辺は再追加されるまで再び消されない。

削除時の走査を辺単位で課金し、全queryでの総走査量を追加回数に抑える。

問題固有の要素

孤立頂点数は辺集合全体ではなく、更新で次数0の境界をまたぐ頂点だけを見れば保てる。

別の問題へ持ち帰る視点: 大域的な個数を問われても、1更新で状態が変わり得る要素を局所化して差分管理する。

正当性

頂点vから削除される各辺は、それ以前の追加queryで存在するようになった辺である。したがって全削除queryを通した隣接頂点列挙回数は辺追加回数以下に償却できる。 局所的な次数0↔正の変化だけを反映でき、削除対象の隣接頂点も直接列挙できる。

実装上の注意

  • 全辺削除中にvの集合そのものを変更するとiteratorが無効化され得るため、隣接先を走査して相手側だけを消し、v側は走査後に一括clearする。

復習の核

  • 同じ辺の再追加、すでに孤立している頂点への削除、次数1の隣接頂点が同時に孤立する例で差分更新を確認する。

計算量と制約

時間

平衡set版O(Q log N)、削除辺の総列挙O(Q)。

空間

O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N\leq 3\times 10^5; 1 \leq Q\leq 3\times 10^5; For each query of the first kind, 1\leq u,v\leq N and u\neq v.; For each query of the second kind, 1\leq v\leq N.; Right before a query of the first kind is given, there is no edge between vertices u and v.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Isolation の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調進行による償却解析

主題
  • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 単調進行による償却解析

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 単調進行による償却解析

      • 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題