99. Number of Connected Components in an Undirected Graph

Medium

Topics

Companies

Helpful tools to learn & understand

Watch key transitions, pointers, and variables update step-by-step.

Open

Read clean, documented implementations across multiple patterns.

View Code

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Input: n = 5, edges = [[0,1],[1,2],[3,4]]

Output: 2

Explanation: Nodes 0, 1, and 2 are connected, and nodes 3 and 4 are connected. There are two connected components.

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]

Output: 1

Explanation: All nodes are connected in a single component.

Input: n = 3, edges = [[0,1],[1,2],[0,2]]

Output: 1

Explanation: Nodes 0, 1 and 2 are all connected to each other forming 1 connected component.

Time Complexity

O(V + E)

Space Complexity

O(V + E)