Kazun の競プロ記録

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

AtCoder Beginner Contest 292 D問題 Unicyclic Components

AtCoder ABC292 ABC 400 pts D問題

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

問題

提出解答

問題の概要

無向グラフ $G=(V,E)$ がある. ただし,

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

とする. このとき, $G$ の全ての連結成分において, その連結成分に含まれる頂点の数と辺の数は等しいか?

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$1 \leq u_j \leq v_j \leq N$

解法

Union Find を利用して, 辺の本数も一緒に記録していくことにより, 全ての辺の追加終了後, 各連結成分における頂点数と辺の数が実際に一致しているかどうかを確認すればよい.

計算量は $O(N+M \alpha (N))$ である.