ABC 446 F — Reachable Set 2

考察

残したい頂点をすべて到達可能にしたうえで、そこから外へ出る最初の頂点を削除すればよい。削除する頂点の組合せを探す前に、「残したい範囲の中だけで全頂点に届くか」と「その範囲から一歩で外へ出る先はどこか」を分けて考える。

残す範囲の到達性と、削除すべき境界

問題の各問を k=ik=i と書き、残したい集合を Pi={1,2,…,i}P_i=\{1,2,\ldots,i\} とする。元の有向グラフを GG、PiP_i の頂点と両端がその中にある辺だけを残した誘導部分グラフを GiG_i と呼ぶ。GiG_i において頂点1から届く集合を RiR_i とする。

まず、目標を達成するには Ri=PiR_i=P_i が必要である。頂点削除で新しい経路は作れない。また、外側の頂点を経由して内側へ届く経路を残すと、その途中の外側頂点も到達可能になってしまう。従って、内側だけで届かない頂点が一つでもあれば答えは −1-1 である。

一方、内側の全頂点に届くなら、内側から直接辺が伸びている外側頂点はすべて削除が必要になる。辺の始点は到達可能なまま残すので、終点を残せば目標に反するためである。それらだけを削除すれば十分でもある。外側へ至るどの経路も、初めて内側から外側へ出るところで削除済みの頂点を通るからだ。

この境界を数えるため、到達集合そのものと、そこから元のグラフで一歩進んだ先を合わせて

Ci=Ri∪{v∣∃u∈Ri, u→v}C_i=R_i\cup\{v\mid \exists u\in R_i,\ u\to v\}

と定義する。CiC_i は頂点番号が ii より大きいものも含む。Ri=PiR_i=P_i のとき、削除する境界は Ci∖PiC_i\setminus P_i なので、答えは ∣Ci∣−i|C_i|-i となる。辺の本数ではなく、異なる終点の個数を数える点に注意する。

有効な頂点と、到達した頂点を分ける

各 ii で探索をやり直すと、それだけで時間は O(N(N+M))O(N(N+M)) になる。削除集合まで列挙するとさらに指数的であり、N,M≤3×105N,M\leq 3\times 10^5 には間に合わない。そこで、ii を1から増やして、GiG_i に新たに加わる頂点だけを有効化する。ここで有効とは「番号が現在の ii 以下で、探索に使ってよい」という意味であり、頂点1から届くこととは区別する。

頂点と辺を追加しても既存の経路は失われないので、RiR_i と CiC_i は増加するだけである。前段階の探索結果を保存し、新たに到達できた頂点からだけ探索を再開したい。ただし、未有効の頂点を見つけたときに、その先へ探索を進めてはいけない。その頂点へ一歩で届くという情報だけを保存し、有効になる段階まで待つ。

頂点番号を添字とする二つの真偽値配列と、その個数を保つ。各段階の探索が終わった時点で、意味は次のようになる。

  • seen[v]: v∈Riv\in R_i である。reachableCount はその個数 ∣Ri∣|R_i|。
  • covered[v]: v∈Civ\in C_i である。coveredCount はその個数 ∣Ci∣|C_i|。

covered は、範囲内での到達済み印ではない。例えば、到達済みの頂点から頂点5へ辺があっても、現在 i=2i=2 なら covered[5] だけを真にし、seen[5] は偽のままにする。

初期値は全頂点の seen を偽、reachableCount=0 とする。covered は頂点1だけを真にし、coveredCount=1 とする。頂点1は辺を通らずに自分自身へ届くため、最初の探索の種になる。それ以外の covered は偽である。

段階 ii では、まず頂点 ii を有効にする。covered[i] が真なら、頂点1自身か、前段階で到達済みの頂点から辺が伸びている頂点なので、ここから探索を始める。偽なら、この段階では探索を始めない。

探索で新たな頂点 uu に届いたら、その全出辺 u→vu\to v を調べる。終点 vv は番号に関係なく covered へ重複なく加える。一方、到達を伝播してよいのは v≤iv\leq i かつ未到達の場合だけである。キューを使うなら、追加時に seen を真にすれば、同じ頂点が重複して入らない。

以下は頂点番号を1始まりとする擬似コードである。out[u] は元のグラフにおける uu の出辺の終点一覧で、未有効頂点への辺も最初から保存しておく。

seen[1..N] = false
covered[1..N] = false
reachableCount = 0
covered[1] = true
coveredCount = 1

for i = 1..N:
    Q = 空のキュー
    if covered[i] and not seen[i]:
        seen[i] = true
        reachableCount += 1
        Q.push(i)

    while Q が空でない:
        u = Q.pop()
        for v in out[u]:
            if not covered[v]:
                covered[v] = true
                coveredCount += 1
            if v <= i and not seen[v]:
                seen[v] = true
                reachableCount += 1
                Q.push(v)

    if reachableCount == i:
        出力 coveredCount - i
    else:
        出力 -1

この方法では、以前に走査した辺を有効化時に読み直す必要はない。未有効の終点へ伸びる辺を調べた時点で covered に印を残しておき、その終点の番号まで進んだときに印を確認するためである。答えが −1-1 の段階でも、探索結果と印は消さずに次へ引き継ぐ。

入力例1で、以前の未到達頂点へも探索が広がる

入力例1の辺は 1→2, 2→4, 2→5, 4→3, 4→51\to2,\ 2\to4,\ 2\to5,\ 4\to3,\ 4\to5 である。各段階の探索終了後は次のようになる。

iiRiR_iCiC_i答え
1{1}\{1\}{1,2}\{1,2\}1
2{1,2}\{1,2\}{1,2,4,5}\{1,2,4,5\}2
3{1,2}\{1,2\}{1,2,4,5}\{1,2,4,5\}−1-1
4{1,2,3,4}\{1,2,3,4\}{1,2,3,4,5}\{1,2,3,4,5\}1
5{1,2,3,4,5}\{1,2,3,4,5\}{1,2,3,4,5}\{1,2,3,4,5\}0

i=2i=2 で頂点2の出辺を調べると、頂点4と5に covered の印が付くが、まだ探索はしない。i=3i=3 では covered[3] が偽なので頂点3に届かず、答えは −1-1 となる。

i=4i=4 で初めて頂点4から探索を始め、4→34\to3 によって、番号がより小さい頂点3にも新たに届く。頂点3は前の段階で有効になっていたが、まだ到達していなかった。このように、探索対象は新しい頂点だけではなく、そこから届く「有効かつ未到達」の全頂点である。また、頂点5には既に印があるので、4→54\to5 を調べても coveredCount は増えない。

典型の発動条件

増分 reachability

頂点を追加する順序に沿って、始点からの到達性を繰り返し問うときに候補になる。追加によって到達性が失われず、探索再開のきっかけを保存できるなら、新規到達頂点の出辺だけを処理できる。頂点や辺の削除を含む場合には、この増加だけの性質は使えない。

到達境界の必要十分化

始点から届く集合を指定集合に一致させたいときは、集合内部での到達性と、外へ出る最初の一歩を分ける。本問では指定集合の全頂点を残す必要があるので、一歩先の外側頂点はどれも削除が必須になる。内部の頂点も削除できる一般の最小カットへ、そのまま同じ結論を使うことはできない。

問題固有の要素

残したい集合が頂点番号の先頭から一つずつ増えるため、境界に見つけた頂点番号が、その頂点を探索に使える時点にもなる。未有効の終点に印を残すだけで、入辺を改めて調べずに探索を再開できる。削除集合の最適化を考える前に、要求される到達集合がどの順序で変わるかを見ることが、この処理につながる。

正当性

段階 ii で新しく使える頂点は ii だけなので、新たな到達経路は必ず頂点 ii を通る。i>1i>1 なら、その経路が初めて頂点 ii に入る直前までは Gi−1G_{i-1} 内の経路である。従って、新たな到達が生じるには、前段階の到達集合から頂点 ii への辺が必要であり、これは開始時の covered[i] で判定できる。i=1i=1 では初期化した印から始点の探索を開始する。

頂点 ii から有効な出辺をたどり、未到達頂点だけをキューへ加えると、新しい到達経路をすべて探索できる。以前に到達した頂点を再処理する必要はない。その出辺のうち、以前から有効な終点は探索済みであり、今回有効になる終点は頂点 ii だけだからである。無効な頂点には進まないので、探索終了時の seen はちょうど RiR_i を表す。

頂点1に最初から印を付け、新規到達頂点の全出辺先へ一度ずつ印を付けるので、探索終了時の covered はちょうど CiC_i を表す。各頂点は seen になる時点で既に covered でもあるため、到達集合自身も漏れない。

目標を達成できるなら、残したい各頂点への経路はすべて PiP_i の中に収まり、Ri=PiR_i=P_i が必要である。逆にこの等式が成り立つなら、Ci∖PiC_i\setminus P_i の各頂点は内側からの出辺の終点なので削除が必須であり、すべて削除すれば外へ出る経路を最初の一歩で遮断できる。よって reachableCount が ii 未満なら −1-1、等しければ coveredCount から ii を引いた値が最小削除数である。

実装上の注意

  • covered の更新には番号の制限を付けず、seen の更新には必ず v≤iv\leq i を要求する。一つの配列で兼用すると、未有効頂点を経由する経路を使ってしまう。
  • キューへの追加時に seen を真にする。自己ループや有向閉路があっても同じ頂点を再投入しない。多重辺や複数の始点から同じ終点への辺はそれぞれ読むが、covered が偽のときだけ個数を増やす。
  • 有向辺の向きを保つ。例えば 3→13\to1 があっても、頂点1から頂点3へ届くとは限らない。無向グラフの連結性を管理するDSUでは、ここで必要な到達性を判定できない。
  • 入力例2では、1→11\to1 で頂点1を二重に数えず、3→13\to1 が2本あっても頂点3は到達済みにならない。頂点2は出辺を持たなくても、入辺 1→21\to2 によって i=2i=2 で到達済みになる。頂点3の出辺 3→53\to5 は探索されないので、答えは順に 1,0,−1,−1,−11,0,-1,-1,-1 となる。
  • 最大で NN 頂点が連なる経路を探索する。再帰DFSの深さによるスタック不足を避けるには、上のキューか明示的なスタックを使う。

復習の核

  • 到達集合を指定されたら、まず集合内だけで各頂点へ届くかを調べ、外へ出る経路の「最初の外側頂点」に注目する。
  • 頂点が有効になったことと、始点から届いたことは別である。今回の追加から、以前に有効になった未到達頂点へも探索が広がりうる。
  • 到達性が増えるだけなら、未有効の行き先には印を残して待つ。後で探索を再開する条件まで設計してから、各出辺を一度だけ読む実装へ落とし込む。

計算量と制約

時間

隣接リストの構築は O(N+M)O(N+M)。有効化時の covered[i] の確認と答えの出力は各頂点につき一度で、合計 O(N)O(N)。各頂点をキューへ加えるのは高々一度なので、その頂点の出辺一覧も高々一度しか走査しない。各辺では covered と seen の定数回の判定・更新だけを行うため、全段階を通した辺の処理は O(M)O(M) である。従って全体の時間計算量は O(N+M)O(N+M)。各段階で全辺を走査するわけではない。

空間

出辺の隣接リストが O(N+M)O(N+M)、二つの真偽値配列とキューが O(N)O(N) で、全体は O(N+M)O(N+M)。逆向きの隣接リストや境界を管理する平衡二分探索木は不要である。

制約との対応

公式制約は 2≤N≤3×1052\leq N\leq 3\times 10^5、1≤M≤3×1051\leq M\leq 3\times 10^5 で、時間制限は2秒、メモリ制限は1024 MiBである。頂点と辺に比例する処理量・記憶量に収まる。連結性は仮定せず、自己ループと多重辺も許す。i=Ni=N では全頂点に届くなら CN=RN=PNC_N=R_N=P_N なので答えは0、届かない頂点があれば最後まで −1-1 となる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 状態グラフのモデリングと探索

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 状態グラフのモデリングと探索

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

      学習の位置

      体系上の位置: 状態グラフのモデリングと探索

      • 暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題