Data Structures19 sections · 729 units
Open in Course

Problem - Number of Connected Components

Classic Union-Find application

Given nn nodes labeled from 00 to n1n-1 and a list of undirected edges, count the number of connected components in the graph.

Example: n=5n = 5, edges =[[0,1],[1,2],[3,4]]= [[0,1], [1,2], [3,4]] returns 22 (components {0,1,2} and {3,4}). You're solving the canonical Union-Find problem.

Union all edges, then count distinct roots. Constraints: nn from 11 to 20002000, edges from 00 to 50005000.