Number of Connected Components In An Undirected Graph

The problem

You are given n, the number of nodes (also called vertices) in an undirected graph, numbered 0 to n - 1, and edges, a list of pairs. A pair [a,b] is an edge that joins nodes a and b in both directions, and the same edge may be listed more than once. A connected component is a group of nodes in which every node can be reached from every other by following edges, and from which no edge leads out. A node with no edges is a component by itself. Return the number of connected components. With no nodes at all the answer is 0.

What to write

function solve(n: number, edges: number[][]): number

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

Output
2

Input
n = 3
edges = []

Output
3

Constraints

0–200 vertices; undirected edges with valid IDs; repeated edges allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 200 nodes, so speed is not the hard part. The care is in the counting. A node with no edges is a component by itself, and n can be 0. Edges can link nodes that are already connected another way, or repeat, so the number of edges alone does not give the answer.

2. Hint 2: Ask a smaller question

   Start with 5 separate nodes, which is 5 groups. Add the edge [0,1] and count the groups. Add [1,2] and count again. Now add [0,2]. Which of the three edges changed the number of groups, which one did not, and what is different about that one?

3. Hint 3: Name the pattern

   Each edge either joins two groups into one or lands inside a single group, and you must tell which, edge after edge, while groups only ever grow. That is the signal for union-find. Union-find keeps nodes in groups with two operations: find tells which group a node is in, and union merges two groups. Read the lesson on union-find.

4. Hint 4: State the invariant

   Each group has one root, the node you end at when you follow parent links upward. The count always equals the number of groups made by the edges handled so far: it starts at n and drops by one exactly when an edge's two ends have different roots.

5. Hint 5: Sketch the pseudocode

   Make every node its own parent and set count to n. To find a root: while a node is not its own parent, point it at its grandparent and move there. For each edge, find the roots of both ends. If they differ, make one root the parent of the other and subtract 1 from count. Return count.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Give each vertex its own disjoint set. Find roots with path compression and merge different roots; each successful merge removes one component.

The slow way

Give every node a label, at first its own number, and count n groups. For each edge whose two ends have different labels, change every node that carries the first end's label to the second end's label, and count one group fewer. It is correct, but each relabeling walks all n nodes. Walking the graph from each unvisited node, as in Number of Islands, is also correct, and fast.

The insight

A group does not need the same label on every member. It is enough that each node has a parent link and that following the links from any member ends at one node, the group's root. Then merging two groups is a single change: make one root the parent of the other. This structure is called union-find: find is the walk up to the root, union is that one change.

Step by step

1. Start every node as the root of its own group. No edge has been read, so no node is connected to another. A node that is its own parent is a root, and each node starts as one. These separate groups are what the Approach calls disjoint sets.
2. Find a node's root: climb the parent links, halving the path as you go. Two nodes are in the same group exactly when their climbs end at the same root. Pointing each visited node at its grandparent halves the path for the next climb. This is one form of path compression.
3. Start the count at n: so far every node is a group by itself. Starting from n means a node that never appears in an edge is still counted as one group, and with no nodes at all the answer is 0.
4. Take each edge and find the roots of both ends. The roots tell you whether the edges used so far already connect the two ends. The order of the edges does not matter here: any order ends with the same groups.
5. Different roots: join the two groups and count one group fewer. Making one root the parent of the other turns two groups into one, so there is one group fewer. When the roots are equal the edge lies inside one group, and nothing changes.
6. After the last edge, the count is the number of components. Every edge has been used, so the groups are exactly the connected components: two nodes share a group when some chain of edges links them, and not otherwise.

The same numbered steps are the comments in each solution.

function solve(n, edges) {
  // 1. Start every node as the root of its own group
  const parent = Array.from({ length: n }, (_, i) => i);
  // 2. Find a node's root: climb the parent links, halving the path as you go
  function find(x) {
    // A root is its own parent, so the climb stops there.
    while (parent[x] !== x) {
      // Point the node at its grandparent, then move up to it.
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  // 3. Start the count at n: so far every node is a group by itself
  let count = n;
  // 4. Take each edge and find the roots of both ends
  for (const [a, b] of edges) {
    const x = find(a),
      y = find(b);
    // 5. Different roots: join the two groups and count one group fewer
    if (x !== y) {
      parent[x] = y;
      count--;
    }
  }
  // 6. After the last edge, the count is the number of components
  return count;
}

function solve(n: number, edges: number[][]): number {
  // 1. Start every node as the root of its own group
  const parent = Array.from({ length: n }, (_, i) => i);
  // 2. Find a node's root: climb the parent links, halving the path as you go
  function find(x: number): number {
    // A root is its own parent, so the climb stops there.
    while (parent[x] !== x) {
      // Point the node at its grandparent, then move up to it.
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  // 3. Start the count at n: so far every node is a group by itself
  let count = n;
  // 4. Take each edge and find the roots of both ends
  for (const [a, b] of edges) {
    const x = find(a),
      y = find(b);
    // 5. Different roots: join the two groups and count one group fewer
    if (x !== y) {
      parent[x] = y;
      count--;
    }
  }
  // 6. After the last edge, the count is the number of components
  return count;
}

def solve(n, edges):
    # 1. Start every node as the root of its own group
    parent = list(range(n))

    # 2. Find a node's root: climb the parent links, halving the path as you go
    def find(node):
        # A root is its own parent, so the climb stops there.
        while parent[node] != node:
            # Point the node at its grandparent, then move up to it.
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node

    # 3. Start the count at n: so far every node is a group by itself
    count = n
    # 4. Take each edge and find the roots of both ends
    for a, b in edges:
        root_a, root_b = find(a), find(b)
        # 5. Different roots: join the two groups and count one group fewer
        if root_a != root_b:
            parent[root_a] = root_b
            count -= 1
    # 6. After the last edge, the count is the number of components
    return count

Example 1, traced

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

Output
2

Why it works

The count starts at the number of groups with no edges, which is n. Each edge either joins two different groups, and then the count drops by one, or it lies inside one group and changes nothing. So after every edge the count is still the number of groups, and at the end the groups are the components.

Time and space

Time O((V + E) log V) amortized bound for path compression alone, extra space O(V). V is the number of nodes (n), E of edges. Each edge costs two finds. Path compression alone, with no smaller-under-larger rule, keeps all finds within about (V + E) log V steps. Amortized means that total is for the whole run, not one find. One list holds V parents.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Subtract one only when the two roots differ. Subtracting for every edge counts an edge inside a group as a merge: 3 nodes with the edges [0,1], [1,2], [2,0] give 0 instead of 1.
• Join the two roots, not the two ends. Take 3 nodes and the edges [0,1], [0,2], [1,2]: pointing the first end at the second moves node 0 from under 1 to under 2, and the result is 0, not 1.
• A node with no edges is still a component. Start the count at n, not at the number of nodes that appear in edges: in example 2, with 3 nodes and no edges, that would return 0 instead of 3.

Pattern

Union-find. Builds on Redundant Connection and Number of Islands.

Keep going