ABC 284 E — Count Simple Paths

考察

数える対象は頂点1から始まる単純pathであり、DFS中の現在の再帰stackがそのまま1本のpathを表す。

答えは10^6へ達した時点で打ち切ってよいので、指数個になり得る単純pathを最後まで列挙する必要はない。

採用する候補: 現在path上の頂点だけをvisitedにし、進入時に1本を数えて未訪問neighborへDFSし、復帰時にunmarkする。

棄却する候補: 一度訪れた頂点を探索終了までvisitedのままにする通常の到達性DFS。

同じ頂点へ別の単純pathから到達する場合まで捨て、path本数を過小評価する。

棄却する候補: 上限を考えず全単純pathを列挙してから10^6との最小値を取る。

単純path数は指数的になり得て、答えが早く上限へ達する入力でも探索が終わらない。

visited[1]=trueとしてDFS(1)を始め、各呼出しの冒頭でcountを1増やす。countが10^6なら終了flagを立てて全再帰から戻る。各neighborについて未訪問ならmarkして再帰し、戻ったらunmarkする。最後にcountを出力する。

典型の発動条件

backtracking DFS

発動条件: 単純pathや重複なし列を列挙し、使用済み集合が現在候補にだけ依存するとき。

再帰の前後で頂点をmark/unmarkしてpath上の重複だけを禁止する。

上限付き列挙

発動条件: 必要な答えがmin(候補数,C)で、Cが十分小さいとき。

C件見つけた時点で終了を全再帰へ伝播する。

問題固有の要素

最大次数10なので、10^6個を見つけるまでの各DFS状態から試すedge数も小さく抑えられる。

別の問題へ持ち帰る視点: 列挙数にcapがある探索では、訪問状態数だけでなく各状態の分岐確認量も合わせて実行可能性を判断する。

正当性

頂点vへ入った瞬間のstackは始点1からvまでの新しい単純pathなので、長さ0のpathも含めて各呼出しを1回数えればよい。 visitedはgraph全体の確定情報ではなく現在pathの禁止集合であり、backtrack時の解除が数え上げの核心になる。 単純性を保ちながら異なるpathで同じ頂点を再利用でき、上限到達時には探索全体を直ちに終了できる。

実装上の注意

  • 終了flagまたはcount判定を各loopと再帰復帰直後に確認し、10^6到達後に別branchへ進まない。
  • 頂点1だけのpathも数えるため、edgeを選ぶ前に現在状態を加算する。

復習の核

  • 三角形で1→2→3と1→3がともに数えられることを手計算し、2から戻った後に頂点をunmarkする位置と上限終了の伝播を確認する。

計算量と制約

時間

O(min(P,10⁶)Δ+N+M)、Pは単純path数、Δ≤10。

空間

O(N+M)、path visitedとDFS stack。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right); 1 \leq u_i, v_i \leq N; The given graph is simple.; The degree of each vertex in the given graph is at most 10.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Count Simple Paths の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: backtracking・可逆な探索状態

主題
  • backtracking・可逆な探索状態: 再帰の前後で使用状態を対称に更新・復元し、現在pathだけの制約を保って探索木を漏れなく列挙できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: backtracking・可逆な探索状態

    補助タグ: 有界全列挙・有限case分解

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

    学習の位置

    体系上の位置: backtracking・可逆な探索状態

    • 再帰の前後で使用状態を対称に更新・復元し、現在pathだけの制約を保って探索木を漏れなく列挙できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題