Number of Connected Components

Difficulty: Easy · Topic: Graphs

Given n nodes labelled 0…n-1 and a list of undirected edges ([a, b]), return the number of connected components. Use union-find (or a BFS/DFS from each unvisited node).

Examples

count_components(5, [[0,1],[1,2],[3,4]])
→ 2

{0,1,2} and {3,4}.

count_components(5, [[0,1],[1,2],[2,3],[3,4]])
→ 1

Target complexity: time O(V + E α(V)), space O(V)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.