Number of Connected Components in an Undirected Graph
Given n nodes labelled 0 to n − 1 and a list of undirected edges, return the number of connected components.
A way to picture it
A room full of strangers, each their own group of one. Every handshake between two different groups merges them into one bigger group. Count the groups that are left when the handshakes stop.
How to approach it
Start with n components. For each edge, union the endpoints; every union that actually merges two different roots removes one component.
Example
Input: {"n":5,"edges":[[0,1],[1,2],[3,4]]}. Output: 2.
Complexity: O((n + E) · α(n)) time and O(n) space. Near-constant time per union/find.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.