112. Connected Components in an Undirected Graph
Group vertices by whether undirected paths connect them and count the groups. All declared vertices belong to the graph, including vertices that occur in no edge.
Isolated vertices each contribute one component. Duplicate edges and self-loops must follow the contract without artificially adding new components.
Example 1
Input
n=5, edges=[[0,1],[1,2],[3,4]]
Output
2
Explanation: The components are {0,1,2} and {3,4}.
Example 2
Input
n=4, edges=[[0,1],[1,0],[2,2]]
Output
3
Explanation: Only the first occurrence joins two sets; 2 and the absent-from-edges vertex 3 are isolated components.
Example 3
Input
n=0, edges=[]
Output
0
Explanation: The empty universe has no components.
Example 4
Input
n=4, edges=[]
Output
4
Explanation: The vertex count, not observed endpoints, defines the universe.
Constraints
0 <= n <= 1050 <= edge occurrences <= 2 * 1050 <= vertex label < n
Hints
Hint 1
Begin with n components, not with the number of observed endpoint labels.
Hint 2
For each undirected pair, find both representatives.
Hint 3
Attach smaller to larger only when roots differ, decrementing once.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Two components after a sparse chain
5
[[0,1],[1,2],[3,4]]
2