Count Connected Components in an Undirected Graph

You are given an undirected graph with \(n\) vertices labeled from 1 to \(n\) and \(m\) edges. Your task is to count the number of connected components in the graph.

Definition: A connected component is a set of vertices where each pair of vertices is connected by some path. Formally, if we denote the graph as \(G=(V, E)\), two vertices \(u\) and \(v\) are in the same connected component if there exists a path from \(u\) to \(v\).

Use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and count the number of times a new traversal is started, which indicates a new connected component. Note that isolated vertices are considered as individual components.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) (1 \(\leq\) \(n\) \(\leq\) 10⁵) is the number of vertices and \(m\) is the number of edges.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) (1 \(\leq\) \(u, v\) \(\leq\) \(n\)), representing an undirected edge between vertex \(u\) and vertex \(v\).

outputFormat

Output a single integer representing the number of connected components in the graph.

5 3
1 2
2 3
4 5

2