Medium · Disjoint Set Union
Understand → Visualise → Practice.
For an undirected graph with vertices 0 through n−1, return its number of connected components.
Start with n singleton sets. Each edge that joins two different sets merges them and reduces the count by one; edges inside a set change nothing.
parent[i] = i and count = n.
Find both roots with path compression; if they differ, link the smaller tree under the larger and decrement count.
The remaining number of sets is the number of components.
O((n + e) α(n)) time and O(n) space with compression and union by size.
Decrementing on a repeated edge reports too few components.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.