LeetCode 323 · Graphs

Number of Connected Components in an Undirected Graph, explained with a picture

Counting circles of friends.

MediumGraphs
▶ Watch it step by step

The problem

Given n nodes and a list of undirected edges, count the number of connected components (separate groups).

Input:  n = 5, friendships 0-1, 1-2, 3-4
Output: 2

Picture it

Picture people and the friendships between them. Everyone starts in their own circle of friends. Each friendship merges two circles into one (if they weren’t already the same). Start with n circles; every successful merge reduces the count by 1.

How to recognise it

  • An undirected graph given as n nodes and a list of edges, and the question is how many separate groups it has.
  • Nodes are joined by connection only, with no direction and no distances.
  • Edges can be processed in any order, which suits a structure that merges groups.
  • With up to 2,000 nodes and 5,000 edges the numbers are small, but the technique matters for 10^5 or more.

Start with brute force

Give each node a group label. For each edge, if the two ends have different labels, relabel every node of one group with the other label. The answer is the number of distinct labels.

def count_components_brute(n, edges):
    label = list(range(n))
    for a, b in edges:
        la, lb = label[a], label[b]
        if la != lb:
            label = [la if x == lb else x for x in label]
    return len(set(label))

Every merge rewrites all n labels, and there can be n − 1 merges, so time is O(V·E) in the worst case: about 10^7 steps for 2,000 nodes and 5,000 edges, but 10^10 for 10^5 of each. Space is O(V).

From brute force to the idea

  1. Find the waste. Relabelling n nodes just to say "these two groups are now one" is far too much work.
  2. Point instead of relabel. Give each group a single representative. Each node holds a parent; following parents leads to the representative, found by find.
  3. Merge with one assignment. To join two groups, make one root the parent of the other: parent[rb] = ra. The other nodes are not touched.
  4. Keep the count. Start with groups = n. Each edge whose ends have different roots merges two groups, so subtract 1. Edges inside an existing group change nothing.
  5. Keep chains short. parent[x] = parent[parent[x]] halves the path while walking, so later find calls are quick.

The key idea: components = n − (number of successful merges), and a merge costs almost nothing.

The key idea

Union-find: components = n − (number of successful unions).

Python solution

def count_components(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    groups = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
            groups -= 1
    return groups

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(V·E): each merge rewrites up to V labelsO(V): the label list
Union-find (shown code)O(V + E log V) at worst, close to O(V + E) in practice, because path halving keeps chains shortO(V): the parent list

Edge cases

  • No edges (n = 5, []): returns 5, since every node is alone.
  • One node (n = 1): returns 1.
  • No nodes (n = 0): returns 0.
  • Duplicate edges and self-loops (n = 3, [[0,1],[0,1],[2,2]]): return 2. A repeated edge and a self-loop find equal roots and change nothing.
  • A chain ([[0,1],[1,2],[3,4]] with n = 5): returns 2.
  • Isolated nodes count as groups, so n must be given and cannot be inferred from the edges.

Common mistakes

  • Counting groups by looking only at nodes that appear in an edge, which forgets isolated nodes.
  • Setting parent[b] = a instead of parent[rb] = ra, which overwrites an earlier link and loses a merge.
  • Decrementing groups for every edge, including ones inside a group.
  • Forgetting that groups starts at n, not 0 or 1.
  • Doing a fresh DFS from every node without a visited set.
Your turn: groups after each edge

Edges arrive one by one. Return a list with the number of groups after each edge is added. For n = 4 and edges [[0,1],[1,0],[2,3],[1,2]] the answer is [3, 3, 2, 1]. Describe what changes, then write it if you like.

Compare with our answer

The same union-find already tracks the count as it goes, so record it after every edge instead of returning it once at the end.

def counts_after_each(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    groups, out = n, []
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
            groups -= 1
        out.append(groups)
    return out

Time O(V + E log V), space O(V + E) for the output. A repeated edge leaves the count unchanged.

A strong answer mentions: appending the count after every edge, that union-find handles edges arriving online, and that a full search per edge would cost O(E·(V + E)).

Check what stuck

1. Friend requests arrive one at a time among 10^5 users. After each request you must report how many friend circles exist. Which approach fits best?

2. Why does the shown code start with groups = n?

3. A learner replaces parent[rb] = ra with parent[b] = a. Which input now returns a wrong count?

Score 60% or more and the lesson is marked complete.