Well, a very common method for graphs...
Vitaliy Goldstein, during the Winter School, discussed graphs, focusing on white, black, and gray vertices, and how many graph problems can be tackled using the depth-first search method. However, as he wrapped up, he digressed into the challenges of a programmer's life and forgot to present one last problem to the participants of the Winter School in Kharkiv 2011. Not wanting to miss the chance to engage his audience, even remotely, he asked us to share this problem with everyone. As a dedicated lecturer, he believes in seizing every opportunity to challenge his audience, no matter how simple the problem might be.
Here is the problem, which can be solved using the depth-first search method: “You are given an undirected graph with N vertices and M edges (1 ≤ N ≤ 20000, 0 ≤ M ≤ 200000). The graph has no loops or multiple edges. Determine the connected components of the given graph.”
Input
The graph is provided in the input file as follows: the first line contains the numbers N and M. Each of the next M lines describes an edge with two integers ranging from 1 to N, representing the endpoints of the edge.
Output
Output a single line containing the number L, which is the number of connected components in the given graph.