考察
各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.
出典