Kazun の競プロ記録

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

AtCoder Beginner Contest 291 E問題 Find Permutation

AtCoder ABC291 ABC 500 pts E問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の並び替え $(A_1, A_2, \dots, A_N)$ がある.

このとき, 以下の $M$ 個のことが分かっている.

$A_{X_j} \lt A_{Y_j} \quad (j=1,2, \dots, M)$

$A$ を一意に特定できるか? 一意ならばその $A$ を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq X_j, Y_j \leq N$
入力に矛盾しない $A$ が存在する.

解法

以下の事実が成り立つ.

$D=(V,E)$ を $N$ 頂点の DAG であるとする. このとき, 以下は同値である.

(a) $D$ の Topological Sort は唯一である.
(b) $D$ ある Topological Sort を $(T_1, \dots, T_N)$ とする. このとき, $i=1,2, \dots, N-1$ に対して, $\overrightarrow{T_i T_{i+1}} \in E$ である.

証明

(b) $\Rightarrow$ (a) は明らかである.

(b) が成り立たないとする. つまり, Topological Sort $(T_1, \dots, T_N)$ において, $\overrightarrow{T_j T_{j+1}} \not \in E$ となる整数 $j$ が存在するとする. このとき, $(T_1, \dots, T_{j-1}, T_{j+1}, T_j, T_{j+2}, \dots, T_N)$ も $D$ の Topological Sort になってしまい, (a) が成り立たない.

ここで, 次のような有向グラフ $D=(V,E)$ を作成する.

$V:=\{1,2, \dots, N\}$
$E:=\left\{\overrightarrow{X_j Y_j} \middle| j=1,2, \dots, M \right\}$

このとき, 制約から $D$ の Topological Sort $(T_1, \dots, T_N)$ が存在する. これが Topological Sort になることと, 実際, $A_{T_i}=i$ となる $A$ が条件を満たすことが同値になるからである.

よって, 上で示した同値性により, Topological Sort において, 隣接している $2$ 点間に有向辺が存在するかどうかを判定すれば良い.

計算量については $O(N)$ 時間である.