Command Palette

Search for a command to run...

Hectal
Problem 25.1 · Union-Find (DSU)Medium

Number of Connected Components in an Undirected Graph

PatternUnion-FindGraph DFS and Flood Fill

What it teaches: Start with n groups; every successful union removes one.

Practise it on judges as “Number of Connected Components in an Undirected Graph”.

The problem

Given n nodes and a list of undirected edges, return the number of connected components.

Example 1

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

Constraints

  • 1 ≤ n ≤ 2000

Pattern clues in the wording

  • → Count groups after adding edges

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int countComponents(int n, int[][] edges) {
        return n;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
n = 5
edges = [[0,1],[1,2],[3,4]]
2
2
n = 5
edges = [[0,1],[1,2],[2,3],[3,4]]
1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Union-find counter · O(E α(n))
1

Union-find counter

Time O(E α(n)) Space O(n)

groups = n; for each edge, if union succeeds, groups--.

Approach 1
class Solution {
    private int[] parent;

    public int countComponents(int n, int[][] edges) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int groups = n;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a != b) { parent[a] = b; groups--; }
        }
        return groups;
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: No adjacency list needed.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No edges (n components)
  • Duplicate edges

Mistakes people make

  • Decrementing on every edge, including ones inside a group.

Interview

Follow-up questions

And with DFS?