Kazun の競プロ記録

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

AtCoder Beginner Contest 231 D 問題 Neighbors

AtCoder ABC ABC231 D問題 400 pts

問題

提出解答

問題の概要

$1,2, \dots, N$ の並び替えで, 以下の $M$ 個の条件を全て満たすような並び替えは存在するか?

$A_j$ と $B_j$ は隣接している.

制約

$2 \leq N \leq 10^5$
$0 \leq M \leq 10^5$
$1 \leq A_i \lt B_i \leq N$
$i \neq j \Rightarrow (A_i,B_i) \neq (A_j, B_j)$
入力はすべて整数

解法

条件を満たすような並び替えが存在することと, 以下は同値である.

無向グラフ $G=(V,E)$ を $V=[\![N]\!], E=\{A_j B_j \mid j=1, \dots, M\}$ としたとき, $G$ の各連結成分は孤立点または長さ $1$ 以上のパスである.

証明\ グラフ $G$ が以下を満たすとする. $G$ のパスになっている連結成分の個数を $K$ , 孤立点の個数を $L$ とする. パスになっている連結成分を $P_1, \dots, P_K$ とし, 連結成分 $P_i$ はパスとみなして, $v_{i,1}, \dots, v_{i,h_i}$ の順であるとする. また, 孤立点を $y_1, \dots, y_L$ とする. このとき,

$\underbrace{x_{1,1} \dots x_{1,h_1}}_{P_1} \underbrace{x_{2,1} \dots x_{2,h_2}}_{P_2} \dots \underbrace{x_{K,1} \dots x_{K,h_K}}_{P_K} y_1 \dots y_L$

は条件を満たす $[\![N]\!]$ の並び替えである. 実際, 上において, $1,2, \dots, N$ はちょうど1回ずつ現れる. また, 任意の辺 $A_j B_j$ は必ず何かしらのパスを構成のために使われているから, 条件も満たす.

逆に, 条件を満たすような並び替え $z_1, \dots, z_N$ が存在するとする. グラフ $G'=(V',E')$ を

$V'=[\![N]\!]$
$E'=\{z_i z_{i+1} \mid i=1,2, \dots, N-1\}$

とする. このとき, $G'$ は長さ $N-1$ のパスである. よって, $G$ は $G'$ の部分グラフなので, $G$ 各連結成分は孤立点または長さ $1$ 以上のパスである.

よって, 言い換えたグラフにおいて, 各連結成分が孤立点か, 長さ $1$ 以上のパスかどうかを判定することで存在するかどうかを見ることができる.

ここで, 連結成分が孤立点であることと, 頂点数 $1$ であることが同値であり, 連結成分が長さ $1$ 以上のパスであることと, 以下をすべて満たすことが同値である.

頂点数 $2$ 以上
各頂点の次数が $2$ 以下
次数 $1$ の頂点が存在する.

連結成分を調べる方法として, BFS や DFS, Union-Find を利用することにより, 計算量 $O(N+M), O(N+M\alpha(N))$ で求めることができる.