Kazun の競プロ記録

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

AtCoder Beginner Contest 287 C問題 Path Graph?

AtCoder ABC287 ABC C問題 300 pts

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

問題

提出解答

問題の概要

以下の $N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ は Path グラフか?

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

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq u_j,v_j \leq N$
$G$ は単純グラフ

解法

以下の特徴づけを用いる.

無向グラフ $G=(V,E)$ において, 以下は同値である.

$G$ は Path グラフである.
$G$ は木で, 次数が $2$ 以下の頂点が $2$ 個である

ここで, $G$ が木であることと, $G$ が $N$ 頂点のとき, $G$ が $(N-1)$ 辺の連結グラフであることは同値であるため, 以下を全て満たすかどうかを判定すればよい.

$M=N-1$
$G$ は連結である
次数が $2$ の頂点の数が $2$ 個である.

これらはそれぞれ次のように判定すればよい.

入力の $N,M$ から直ちに判定できる.
BFS, DFS, Union-Find を利用することにより, 連結性を判定できる.
$u_1, \dots, u_M, v_1. \dots, v_M$ に登場する $w$ の個数が頂点 $w$ の次数である.

これらを判定することによって, $O(N)$ 時間で判定できる.