Depth-First Search (DFS) - Classic Problems | Repovive

CLS12. Depth-First Search (DFS)

1s256 MB

Given an undirected graph with $n$ vertices and $m$ edges, find the number of connected components.

A connected component is a maximal set of vertices such that there is a path between every pair of vertices in the set.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

$\text{number of connected components}$

Input

Explanation

For this input, the required output is 2.

Output

Input

Explanation

For this input, the required output is 1.

Output

Input

5 0

Explanation

For this input, the required output is 5.

Output

Given an undirected graph with $n$ vertices and $m$ edges, find the number of connected components.

A connected component is a maximal set of vertices such that there is a path between every pair of vertices in the set.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

$\text{number of connected components}$