MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Connected Components in Undirected Graph

1 approach, code in every language

You are given an integer n, representing an undirected graph with nodes labeled from 0 to n - 1, together with a list of undirected edges. Each entry edges[i] = [a, b] means there is an edge connecting node a and node b.

A connected component is a maximal set of nodes such that any two of them are reachable from one another through the edges. Return the total number of connected components in the graph.

Isolated nodes with no incident edges each count as their own component.

Example 1

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

Output: 2

Nodes 0, 1, and 2 are linked into one component, and nodes 3 and 4 form another, so there are 2 components.

Example 2

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

Output: 1

Every node is chained together into a single component.

Constraints

1 <= n <= 2000
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
There are no repeated edges.

Union-Find (Disjoint Set Union)

Start with n isolated groups and merge across every edge; each successful merge drops the count by one.

Loading animation…

Intuition

Two nodes belong to the same component exactly when a path connects them. Union-Find keeps a representative root for every set of connected nodes, so checking whether two nodes are already linked is a quick root comparison. Begin by treating each node as its own component, which gives n separate groups. Every edge that joins two nodes from different groups fuses them and reduces the number of components by one; an edge inside an existing group changes nothing. After all edges are processed, the number of surviving groups is the answer.

Algorithm walkthrough

1Initialize a parent array where each node points to itself, and set a counter equal to n.
2Define find(x) to follow parent pointers up to the root, compressing the path so later lookups are faster.
3For each edge (a, b), locate the roots of a and b.
4If the roots differ, attach one root under the other and decrement the counter.
5If the roots already match, the edge lies inside a known component, so skip it.
6Return the counter after every edge has been consumed.

Implementation

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        count = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                count -= 1
        return count

Time

O((n + E) * α(n))

Space

O(n)

E is the number of edges. Path compression makes each find nearly O(1) amortized, where α is the inverse Ackermann function, so the practical cost is close to O(n + E).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free