Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 284 E問題 Count Simple Paths

AtCoder ABC284 ABC E問題 500 pts

問題

提出解答

問題の概要

単純無向グラフ $G=(V,E)$ が与えられる. なお,

$V:=\{1,2, \dots, N\}$
$E:=\{u_j v_j \mid j=1,2, \dots, M\}$

である. また. 各頂点の次数は $10$ 以下である.

このとき, 頂点 $1$ を始点とする単純パスの数を $K$ としたとき, $\min(K, 10^6)$ を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq \min(2 \times 10^5, \frac{N(N-1)}{2})$
$1 \leq u_j, v_j \leq M$
$G$ は単純
$G$ における各頂点の次数は $10$ 以下である.

解法

DFS によって求めれば良い. また, 実際には次のようにして正解できる.

$K \gets 0$
$v=1,2, \dots, N$ に対して, $F_v \gets 0$ とする.
${\rm dfs}(v)$
- $K$ に $1$ 加算する.
- $K \geq 10^6$ ならば, $10^6$ を返す.
- $F_v \gets 1$
- $v$ の各近傍 $u$ に対して, ${\rm dfs}(u)$ を行う.
- $F_v \gets 0$
- $K$ を返す.
${\rm dfs}(1)$ を行い, $K$ を出力する.

この打ち切りを行うことによって, $K':=\min(K, 10^6)$ とすると, 計算量について, 各頂点の次数が $10$ 以下なので, 最大次数を $\Delta$ として, $O(\Delta K')$ 時間となる.