Graphs · pattern 6 of 8

Union-find

Union-find keeps items in groups. Each item holds one pointer towards the leader of its group, also called the root, and a leader points at itself. Find follows the pointers up to the leader. Union merges two groups by pointing one leader at the other.

Watch it run in the app

When to use it

Use it when links are added one at a time and, between them, you must know whether two items are already in the same group.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

A club has 5 members, numbered 0 to 4, and each starts alone. Read the log in order. An entry ["join", a, b] merges the groups of a and b. An entry ["ask", a, b] asks whether a and b are in one group now. Return the answers in order.

Input
n = 5
log = [["join", 0, 1], ["join", 2, 3], ["ask", 0, 2], ["join", 1, 2], ["ask", 0, 2], ["join", 0, 3], ["ask", 3, 4]]

Output
[false, true, false]

The method

Start every member as the leader of a group of one
Find: climb the pointers to the leader, halving the path
Take the log in order and find both leaders
Union: two different leaders, so point one at the other
An ask: the same leader means the same group
Return the answers

The run, one moment at a time

Step 1. Each of the 5 members points at itself, so each is the leader of a group of one. The row shows where every member points.
```
parent: 0 1 2 3 4
answers: empty
```
Step 3. The first entry joins 0 and 1. Find both leaders first. 0 points at itself and so does 1, so each is its own leader.
```
parent: 0 1 2 3 4
answers: empty
```
Step 4. The leaders 0 and 1 are different, so this is a union: point leader 0 at leader 1. Members 0 and 1 are one group now, and 1 is its leader.
```
parent: 1 1 2 3 4
answers: empty
```
Step 4. Join 2 and 3. Each is its own leader, and the leaders differ, so point 2 at 3. There are 3 groups now.
```
parent: 1 1 3 3 4
answers: empty
```
Step 5. Ask about 0 and 2. The climb from 0 ends at leader 1, and the climb from 2 ends at leader 3. Different leaders mean different groups: false.
```
parent: 1 1 3 3 4
answers: false
```
Step 4. Join 1 and 2. The leader of 1 is 1 and the leader of 2 is 3. Point leader 1 at leader 3: one changed pointer merges two whole groups.
```
parent: 1 3 3 3 4
answers: false
```
Step 2. The same question again: 0 and 2. Find the leader of 0. It pointed at 1, and 1 points at 3, the leader. On the way, 0 is pointed at its grandparent, 3, so its next climb is shorter.
```
parent: 3 3 3 3 4
answers: false
```
Step 5. The leader of 0 is 3 and the leader of 2 is 3. The same leader means the same group: true. Before the last join, this question got false.
```
parent: 3 3 3 3 4
answers: false true
```
Step 4. Join 0 and 3. Both have leader 3, so they are in one group already. No pointer changes.
```
parent: 3 3 3 3 4
answers: false true
```
Step 5. Ask about 3 and 4. Each points at itself, so each is a leader: 3 leads a group of 4 and 4 is alone. Different leaders mean different groups: false.
```
parent: 3 3 3 3 4
answers: false true false
```
Step 6. All 7 entries are read. The 3 answers are false, true, false. Each one took two short climbs, not a walk over a whole group.
```
parent: 3 3 3 3 4
answers: false true false
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(n, log) {
  // 1. Start every member as the leader of a group of one
  const parent = [];
  for (let i = 0; i < n; i++) parent.push(i);
  // 2. Find: climb the pointers to the leader, halving the path
  function find(x) {
    // A leader points at itself, so the climb stops there.
    while (parent[x] !== x) {
      // Point x at its grandparent, then move up to it.
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  const answers = [];
  // 3. Take the log in order and find both leaders
  for (const [kind, a, b] of log) {
    const leaderA = find(a);
    const leaderB = find(b);
    if (kind === "join") {
      // 4. Union: two different leaders, so point one at the other
      if (leaderA !== leaderB) parent[leaderA] = leaderB;
    } else {
      // 5. An ask: the same leader means the same group
      answers.push(leaderA === leaderB);
    }
  }
  // 6. Return the answers
  return answers;
}

Python

def solve(n, log):
    # 1. Start every member as the leader of a group of one
    parent = list(range(n))

    # 2. Find: climb the pointers to the leader, halving the path
    def find(x):
        # A leader points at itself, so the climb stops there.
        while parent[x] != x:
            # Point x at its grandparent, then move up to it.
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    answers = []
    # 3. Take the log in order and find both leaders
    for kind, a, b in log:
        leader_a = find(a)
        leader_b = find(b)
        if kind == "join":
            # 4. Union: two different leaders, so point one at the other
            if leader_a != leader_b:
                parent[leader_a] = leader_b
        else:
            # 5. An ask: the same leader means the same group
            answers.append(leader_a == leader_b)
    # 6. Return the answers
    return answers

How to spot it

Asked: Are these two already connected?: Two items are connected exactly when find gives the same leader for both. No walk along the links is needed.
Given: Links are added one at a time and never removed: Groups only merge and never split. One changed pointer merges two groups, so the structure is right after every new link.
Asked: How many separate groups are there after each new link?: Start the count at the number of items. Each union of two different leaders leaves one group fewer.
Limits: Up to 100,000 items, and 100,000 questions mixed in with the links: A new walk for every question can be about 10 billion steps in all. A find climbs only a few pointers.

Looks like it, but is not

The groups are cells of a grid that touch side by side. Use Grid connected components. A cell's neighbors are known from its position. A walk that spreads from cell to cell finds each group without any pointers.
You need the route between two items, or how many links long it is. Use Breadth-first search by distance. Union-find answers only yes or no. It forgets which links made a group, so it cannot give a route or its length.
Links go one way: from a you can reach b, but not a from b. Use Graph traversal with a visited set. A group has no direction: everyone in it is together. With one-way links, what a reaches must be found by walking.

Cost and mistakes

A find usually climbs a few pointers. One climb can be long, but halving shortens every path it climbs, so m entries take at most about m log n steps in all, O(m log n). Extra space is one pointer for each item, O(n).

Watch out

Join the leaders, not the two items. parent[a] = b separates a from the rest of its group. Find both leaders first, then point one leader at the other.
Two items of one group can have different parents. To test whether they are together, compare find(a) with find(b), never parent[a] with parent[b].

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 2

Redundant ConnectionMedium · Graphs
Number of Connected Components In An Undirected GraphMedium · Graphs