Applications

Union-find answers one kind of question: as connections arrive, which things are now connected? Many problems turn out to be this question in disguise. This lesson shows the common patterns.

Counting groups

Keep a counter of sets. It starts at n, and every union that really joins two sets (returns True) takes 1 away. At any moment the counter is the number of groups. In graph terms (GRPH), the elements are vertices, the connections are edges, and the groups are the connected components.

A search of the graph (breadth-first or depth-first, GRPH) also finds the components, in O(n + m) time for m edges. Union-find wins when the edges arrive one at a time and the question is asked after each one: a search would have to start again every time.

Finding cycles

A cycle is a loop: a way to leave a vertex along edges and come back without using an edge twice. When an edge joins two vertices that are already connected, there was already a path between them, and the new edge closes that path into a cycle. So union returning False means “this edge makes a cycle”. Step through “Roads one by one”.

This is the heart of Kruskal’s algorithm for the cheapest set of edges that connects every vertex (SPAN): take the edges from cheapest to most expensive, and keep an edge only if union returns True.

Grids and islands

A grid of R rows and C columns becomes a list of elements by numbering the cells row by row: cell (r, c) is element r · C + c. Two land cells that touch belong to the same island, so union each land cell with its land neighbours. When the cells are visited in order, it is enough to look up and to the left (the second variant): the neighbours below and to the right will look back.

def count_islands(grid):          # a list of strings of '0' and '1'
    R, C = len(grid), len(grid[0])
    d = DSU(R * C)
    islands = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != '1':
                continue
            islands += 1                # a new island of one cell
            for nr, nc in ((r - 1, c), (r, c - 1)):
                if nr >= 0 and nc >= 0 and grid[nr][nc] == '1':
                    if d.union(r * C + c, nr * C + nc):
                        islands -= 1    # two islands became one
    return islands

For a fixed map, a search is just as good. Union-find is the right tool when land appears one cell at a time and the count is wanted after each change. Practice DSUF-P4 asks for exactly that.

Elements that are not numbers

When the elements are names (variables, email addresses, words), keep the parents in a dict instead of a list. An element enters the structure the first time it is seen:

parent = {}

def find(x):
    parent.setdefault(x, x)       # a new name is its own root
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[ra] = rb

A common use is checking a list of facts such as a == b and a != c. Union every pair that must be equal, then check that no “not equal” pair has ended up in one set. Practice DSUF-P5 does this.

A further step, called weighted union-find, stores a number on every parent link as well, such as “this element is 3 more than its parent” or “this currency is worth 2.5 of its parent”. Find adds up (or multiplies) the numbers along the path, and compression keeps the totals. It answers questions like “how many rupees is one euro, given these exchange rates?”.

What union-find cannot do

• Split a set. There is no cheap way to undo a union. If edges are removed over time, one method is to read the removals backwards: in reverse, every removal becomes an addition.
• List a set’s elements. The links point up, so a set cannot be walked from its root. If the members are needed, keep a list at each root and join the lists in union, always moving the shorter list into the longer one. Each element then moves at most log₂ n times, by the argument of lesson 2.
• Find a path. Union-find says two vertices are connected, not how. For the route itself, search the graph (GRPH).