Kazun の競プロ記録

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

AtCoder Beginner Contest 284 C問題 Count Connected Components

AtCoder ABC284 ABC C問題 300 pts

問題

提出解答

(DFS) atcoder.jp

(Union Find) atcoder.jp

問題の概要

単純無向グラフ $G=(V,E)$ が与えられる. なお,

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

である.

$G$ にある連結成分の数を求めよ.

制約

$1 \leq N \leq 100$
$0 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq u_j, v_j \leq N$
$G$ は単純

解法1

グラフにおけるある頂点を含む連結成分は, BFS, DFS を用いて, 効率的に求めることができる. よって, 次のようにして求めることができる.

$v=1,2, \dots, N$ に対して, $F_v \gets 0$ とする.
$K \gets 0$
の順に以下を行う.
- $F_v=0$ ならば, BFS, DFS によって, $v$ を含む連結成分 $\Gamma$ を求め, 各 $u \in \Gamma$ に対して, $F_u \gets 1$ とし, $K$ を $1$ 増やす.
$K$ を出力する.

これにより, 計算量は $O(N+M)$ 時間である.

解放2

Union Find というデータ構造を利用すると, 合計 $O(N+M \alpha(N))$ 時間で求めることができる.