Union Find Components: Disjoint Set Pattern

Learning Outcome

After this lesson, you should be able to use parent and size arrays to merge graph components efficiently.

Problem Statement

Given n nodes and undirected edges, return the number of connected components using Union Find.

Brute Force Approach

After every edge, run DFS again to recompute groups. This repeats traversal work after each merge.

Optimized Approach

Initialize each node as its own parent. Union endpoints of every edge and decrement the component count only when two different roots merge.

Exact Pseudocode

parent[i] = i
size[i] = 1
components = n
for edge (a, b):
  if union(a, b) merges two roots:
    components -= 1
return components

find(x):
  compress parent pointers until root is found
  

Reference Code

class Solution:
    def countComponents(self, n, edges):
        parent = list(range(n))
        size = [1] * n

        def find(x):
            while x != parent[x]:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
            return True

        components = n
        for a, b in edges:
            if union(a, b):
                components -= 1
        return components
  

Sample Dry Run

Complexity

Edge Cases

• Repeated edges should not reduce the count twice.
• Self-loops should not reduce the count.
• With no edges, every node is a component.

Interview Checklist

• Only decrement count when roots differ.
• Compress paths in find.
• Attach smaller set under larger set.

FAQs

It is the inverse Ackermann factor, which is effectively constant for interview-sized inputs.

It is especially useful when connectivity is built through many merge operations.

Disjoint set union.