LESSON 567 OF 677 · GRAPHS

Number of Connected Components in an Undirected Graph

Practice O((n + e)·α(n))

You get an undirected graph with n nodes, labeled 0 to n - 1. Its edges come as an array edges. Each edges[i] = [a_i, b_i] joins nodes a_i and b_i.

Return how many connected components the graph has.

A connected component is a group of nodes linked by edges. From any node in the group, you can reach every other one. No edge links two different groups. A node with no edges is a component by itself.

Example 1:

Input: n = 6, edges = [[0, 3], [3, 5], [1, 4]]
Output: 3
Explanation: Nodes 0, 3 and 5 are linked.
Nodes 1 and 4 are linked.
Node 2 has no edges at all.
    0 - 3 - 5      1 - 4      2

Example 2:

Input: n = 4, edges = [[2, 0], [0, 1], [1, 2], [1, 3]]
Output: 1
Explanation: All four nodes are linked.
The edge 1 - 2 adds nothing new.
Nodes 1 and 2 are already linked through 0.
    2 - 0
     \ /
      1 - 3

Example 3:

Input: n = 3, edges = []
Output: 3
Explanation: With no edges, each node is a component on its own.

Constraints:

1 to 100,000 nodes.
0 to 100,000 edges.
Each edge joins two different nodes.
Every node in edges is from 0 to n - 1.
No edge is listed twice.

Note:

Your algorithm should run in O((n + e)·α(n)) time, nearly O(n + e), where e is the number of edges, and use O(n) extra space.

The tutorial uses union-find, also called disjoint sets. Every node starts as a group of its own, so there are n components. Each edge merges the groups of its two nodes, unless they are already in the same group, and every merge leaves one component fewer. A group is kept as a tree in which each node points to its parent, and the tree's root names the group: two nodes are in the same group exactly when they lead to the same root. Two tricks keep the trees flat: path halving (on the way up to the root, point each node to its grandparent) and union by size (hang the root of the smaller tree under the root of the larger one). With both, finding a root or merging two groups costs O(α(n)) on average, where α is the inverse Ackermann function, which grows so slowly that it stays below 5 for any n a computer can hold.

A DFS or BFS from every node that isn't visited yet, as in Number of Islands, also counts the components in O(n + e); on a graph this big, use a BFS or a DFS with its own stack, since a recursive DFS down a path of 10⁵ nodes can run out of call stack. Union-find is worth knowing because it keeps working while the edges arrive one at a time: after each new edge it can still tell, almost at once, whether two nodes are connected, without searching the graph again.

STEP 1 OF 20

Guided

Ctrl + Enter to check