考察
reachable setをちょうど{1..k}にするには、誘導subgraphG[1..k]がvertex1から全てconnectedでなければならない。大きいvertexを削除してもこの内部連結性は作れない。内部がconnectedなら、{1..k}からedgeで隣接する外部vertexを全て削除すれば、それ以外の外部vertexは残しても1から到達不能である。これが必要十分かつ最小削除数になる。prefix connected性はDSUにvertex番号maxがk以下となったedgeを追加し、component size of1がkかで判定できる。削除対象は外部vertex単位で数えるため、prefixへのedgeが複数あっても一度だけcountする。
採用する候補: kを昇順sweepし、DSUでprefix連結性、外部隣接vertexのdistinct countをincremental管理する
vertex k追加時に両端≤kのedgeをunionし、境界を跨ぐ外部endpointをset/countへ追加・prefixへ入ったものを除くことで全kをO((N+M)αN)程度で処理できる。
棄却する候補: 各kで大きいvertexを削除したgraphへBFSし、境界隣接を数える
O(N(N+M))でprefix間の単調なedge追加を再利用していない。
adjacencyを使いk=1..Nでvertex kをactivateする。小さい隣接はunionし、大きい隣接をboundary set/countへ登録する。k自身が以前boundaryなら除去する。DSU component(1) size=kならboundary distinct数、そうでなければ-1を出す。
典型の発動条件
prefix-induced connectivity sweep
発動条件: vertex番号prefixごとのconnected性を全て判定するとき。
vertex activateとDSU unionを昇順で行う。
dynamic boundary counting
発動条件: 成長集合に隣接する外部頂点数を重複なく保つとき。
外部endpointのincident count/flagを更新する。
問題固有の要素
外側全削除は不要で、reachable setを漏らす直接境界vertexだけ消せば、その先全体も自動的に切り離される。
別の問題へ持ち帰る視点: reachable setを指定するvertex deletionでは、内部connectivityと外向きvertex boundaryを分離する。
正当性
ちょうどprefixを到達集合にするには内部誘導グラフが連結である必要がある。連結なら外隣接頂点は一歩で到達するため削除必須。これら全てを消すと外へ出る最初の辺がなくなり十分。DSU連結性と相異なる境界頂点数を保つことで最小削除数を得る。
実装上の注意
- 外部vertexへの複数edgeをdistinct countし、kへ昇格したvertexのflagを一度だけ外す。k=1は内部connectedとみなす。
復習の核
- N≤9でdelete subset全探索し、prefix内部非連結、同じ外部vertexへ複数edge、境界の先にだけ繋がるvertexを比較する。
計算量と制約
時間
N 頂点、M 辺。境界flagと DSU で O((N+M)α(N))。
空間
隣接、DSU、境界flagで O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 2 \times 10^{5}; 0 \le M \le 3 \times 10^{5}; 1 \le u_i < v_i \le N\ (1 \le i \le M); (u_i,v_i) \ne (u_j,v_j)\ (1 \le i < j \le M); All input values are integers.
出典