ABC 401 E — Reachable Set

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: DSUによる連結成分管理・縮約

主題
  • DSUによる連結成分管理・縮約: 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: DSUによる連結成分管理・縮約

    補助タグ: event・値順のオフライン走査

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

    学習の位置

    体系上の位置: DSUによる連結成分管理・縮約

    • 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。

    先に読む単元:

    • event順にactive集合を更新する — 値・時刻・座標順にeventを並べ、同値eventの処理順を決めてactive集合を増分更新する。逆向き処理や寄与分解とは不変量が異なるため独立に学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題