Kazun の競プロ記録

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

AtCoder Beginner Contest 285 D問題 Change Usernames

AtCoder ABC285 ABC D問題 400 pts

問題

問題

提出解答

問題の概要

$N$ 人のユーザーがいる. ユーザー $i$ のユーザーネームは現在 $S_i$ である.

$N$ 人のユーザーに対して適切な順番で以下を実行することによって, $i=1,2, \dots, N$ 全てに対して, ユーザー $i$ のユーザーネームを $T_i$ にすることができるか?

ユーザーネームが $T_i$ あるユーザーが存在しないようなユーザー $i$ を選び, ユーザー $i$ のユーザーネームを $T_i$ に変更する.

なお, $S_1, \dots, S_N$ は相異なり, $T_1, \dots, T_N$ も相異なる. また, $S_i \neq T_i$ である.

制約

$1 \leq N \leq 10^5$
$S_i, T_i$ は長さ $1$ 以上 $8$ 以下の英子文字列である.
$S_i \neq T_i$
$S_1, \dots, S_N$ は相異なる.
$T_1, \dots, T_N$ は相異なる.

解法

$S_i=T_j$ となる $(i,j)$ について, ユーザー $i$ のユーザーネームを変更した後に, ユーザー $j$ のユーザーネームを変更しなければならない.

そして, 上記で挙げられる条件を満たすような変更の手順は必ず条件を満たす.

よって, 次で定義される有向グラフ $D=(V,A)$ が DAG かどうかを判定すれば良い.

$V:=\{1,2, \dots, N\}$
$A:=\{\overrightarrow{ij} \mid i,j \in V, T_i=S_j \}$

この有向グラフは高々 $N$ 辺である. よって, $O(N)$ 時間で判定できる.