Kazun の競プロ記録

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

AtCoder Beginner Contest 245 F問題 Endless Walk

AtCoder ABC ABC245 F問題 500 pts

問題

提出解答

問題の概要

単純有向グラフ $D=\left(V=[\![N]\!], A=\left\{\overrightarrow{U_j V_j} \mid j=1,2, \dots, M \right \} \right)$ が与えられる.

無限長の有向パスが存在するような始点の候補はいくつか?

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq \min (N(N-1), 2 \times 10^5)$
$D$ は単純

解法1

$V$ 上の関係 $\to$ を

$u \to v :\iff u$ を始点, $v$ を終点とする有向パスが存在する

と定義する. すると, この $\to$ は反射律と推移律を満たす.

この $\to$ を用いて, $V$ 上の関係 $\sim$ を

$u \sim v :\iff (u \to v) \land (v \to u)$

とすると, $\sim$ は $V$ 上の同値関係である. この同値関係による同値類を強連結成分という.

そして, $V/\sim$ 上の関係 $\geq$ を

$[u] \geq [v] :\iff u \to v$

とすると, この $\leq$ は well-defined な順序関係になる.

従って, $D/\sim:=\left(V/\sim, A/\sim:=\left\{\overrightarrow{[u] [v]} \mid \overrightarrow{uv} \in A \right\} \right)$ は DAG になる.

ここで, $v \in V$ に対して, 以下の2条件は同値になる.

$v$ を始点とする長さ無限の有向パスが存在する.
$\exists w \in V {\rm ~s.t.~} v \to w, \# [w] \geq 2$

証明 (クリックで展開)

解法2

この同値性から, (b) で判定をすることにする.

$D/\sim$ において,

$\displaystyle {\rm DP}[\alpha]=[\# \alpha \geq 2] \lor \bigvee_{\overrightarrow{\alpha \beta} \in A/\sim} {\rm DP}[\beta]$

とすると, $\alpha \in V/\sim$ において,

${\rm DP}[\alpha]=\mathbb{T} \iff \alpha$ の (任意の) 頂点はその頂点の強連結成分における頂点数が $2$ 以上である頂点に到達できる.

である.

以上から,

$\displaystyle \sum_{\substack{\alpha \in V/\sim \\ {\rm DP}[\alpha]=\mathbb{T}}} \# [\alpha]$

が答えである.