Skip to content
Hello Python

Count Components with Union-Find

Practice ExerciseIntermediateMediumArrayGraphUnion-Find

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement component_count(node_count, edges). Nodes are 0..node_count-1. Return the number of connected components after all undirected edges are added.

Starter code

def component_count(node_count, edges):
    pass
Test cases

two-components

{
  "args": [
    5,
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        3,
        4
      ]
    ]
  ]
}

Expected: 2

redundant-edge

{
  "args": [
    3,
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        0,
        2
      ]
    ]
  ]
}

Expected: 1

Wizard outline
  1. Step 1: Count every node as its own component

    Return one component per isolated node before processing edges. Union-Find begins with a forest of singleton roots.

  2. Step 2: Merge one pair of roots

    Decrease the count when an edge joins two distinct nodes. A successful union replaces two components with one.

  3. Step 3: Skip edges inside one component

    Find canonical roots, merge only distinct roots, and compress paths. Root identity is the invariant that distinguishes a real merge from redundancy.

Footguns and prerequisites
  • Decrementing for a redundant edge undercounts components.
  • Skipping path compression can make a long chain unnecessarily expensive.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Use path-compressed find and union by size while maintaining a component counter.

Why it works: Each root represents exactly one component. A union of distinct roots combines exactly two components, so decrementing once preserves the count; redundant edges do not change it.

def component_count(node_count, edges):
    parent = list(range(node_count))
    size = [1] * node_count
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    count = node_count
    for left, right in edges:
        a, b = find(left), find(right)
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        count -= 1
    return count