Connected Components solved by 795

Feb. 21, 2014, 4:23 p.m. by Rosalind Team

Topics: Graphs

Problem

Figure 1. The graph from the dataset

The task is to use depth-first search to compute the number of connected components in a given undirected graph.

Given: A simple graph with $n \le 10^3$ vertices in the edge list format.

Return: The number of connected components in the graph.

See Figure 1 for visual example from the sample dataset.

Sample Dataset

12 13
1 2
1 5
5 9
5 10
9 10
3 4
3 7
3 8
4 8
7 11
8 11
11 12
8 12


Sample Output

3