Disjoint Sets: From Linear to Almost Constant Time

Tracking which items belong to the same group looks trivial, until your inputs get big.

Hi Friends,

Welcome to the 186th issue of the Polymathic Engineer newsletter. This week we look at a data structure that most engineers underestimate the first time they encounter it: the disjoint set, also known as union-find.

The reason why this data structure is often overlooked is that the problem it wants to solve looks very simple. Just keep track of which group each item is in and merge the groups when necessary. However, going for the brute force solution without thinking twice is a trap, because you don’t notice how slow this is until your inputs get bigger.

Let’s make it concrete. Imagine you are building a social app. People send and accept friend requests, and you want to answer two questions quickly: are these two people part of the same circle of friends, and how do you merge the two circles into one when a new friendship forms? At the start, everyone stays in their own circle of size one. As connections form, circles join together, and they can only ever grow: once two circles merge, they stay merged. You never split them back apart.

This is the disjoint set problem in a nutshell. You have a lot of items that are split into separate groups that don’t have anything in common, and you need to join the groups on the go while asking yourself, “Are these two in the same group?”

This problem comes up a lot more often than you might think: connected components in a graph, image segmentation, minimum spanning trees, and clustering in machine learning all lean on it. In this article, we will cover all that you need to know:

• What a disjoint set is

• How to represent it in memory

• The naive implementations: quick find and quick union

• Union by size

• Path compression

• Applications

---

To learn technical skills you must work on real projects. CodeCrafters is a great platform for that. You can build your own Redis, Kafka, DNS server, SQLite, HTTP server, or Git from scratch using your chosen programming language.

---

What a disjoint set is

Let’s start with the name. Disjoint sets are groups of items such that no item is shared between any two groups. Each item is in one group, and the groups never overlap. In the social app example, each group of friends makes up a circle, and nobody can be in more than one circle at the same time.

Each group needs a way to identify itself, so we pick one of its members to behave as the representative of the whole group. You can think of it like the group’s label: every item in the group points back, directly or indirectly, to the same representative. Two items are in the same group if and only if they share the same representative. This is the principle that makes everything work, and we’ll see why when we look at how the structure is stored.

The data structure goes by two names. Some people call it a disjoint set, others call it union-find. That second name gives away the two operations it’s built around:

• Find(x): return the representative of the group that x is in.

• Union(x, y): join the groups that x and y are in into a single one.

On top of these two, it is useful to have a third operation, which tells us whether two objects are already together:

• Same(x, y): check if x and y are in the same group.

Same is essentially just a small wrapper around Find. We run Find on both items and then compare the two representatives. If they match, the items are in the same group. Otherwise, they are in different groups. We’ll keep reusing this idea, because most of the time we don’t care who the representative actually is. We just worry whether two items land on the same one.

One last thing worth saying is that the “is connected to” relation must act sensibly if this grouping is to make any sense. Each item is connected to itself. If A is connected to B, then B is connected to A. And if A is linked to B and B is connected to C, then A is connected to C. That last property is the important one: it’s what lets us merge two circles and think of each member of both as connected, even the pairs that were never directly linked. The data structure doesn’t define this relation for you. It just assumes it behaves this way and takes care of the bookkeeping.

How to represent it in memory

Once we know which operations we need, the next question is how to store everything.

The first thought that comes to mind is to maintain an actual list for each group and a map saying, for each item, which list it is part of. This works, but it has two problems. The first is that you have two structures to keep in sync by hand every time something changes, which is error-prone. The second is related to performance. When you merge two groups, you have to walk through one of the lists and update the mapping of every item in it. So a single merging costs linear time.

We can do much better if we structure each group in the form of a tree, where the root is the representative of the group. However, instead of using classical trees with nodes and link to child nodes, it’s more convenient to use an array. The underlying idea is to give each item an index between 0 and n-1. If your items aren’t integers in that range, you can always map them to an index using a hash table.

So, we use a single array of size n, which we can call parent. The reason of the name is that for each item the array only stores the index of its parent in the group’s tree, and not the full group. The representative of a group is that special item which is its own parent (parent[i] == i). To get from any item to its representative, we follow the parent links upward until we reach an item that points to itself.

In the beginning, each item is in its own group of size one, and therefore each item is its own representative. That means we initialize the array so that every position points to itself: parent[i] = i for all i. In Python, the whole setup fits in the constructor:

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))

That one line sets parent[0] = 0, parent[1] = 1, and so on. We now have n groups, each containing a single item. Every operation we build from here is just based on reading and rewriting entries in this one array.

The naive implementations: quick find and quick union

With the array in place, we have two natural ways to use it. They are at opposite ends of the same trade-off, so it is worth seeing both.

The first method is quick find, which keeps things flat: instead of pointing to a parent somewhere in a tree, every item points directly to its representative. This means that parent[x] is always the representative of x’s group.

Find becomes trivial, since we just read the array and return what is there in constant time:

def find(self, x):
    return self.parent[x]

Same is just as cheap, because it only compares two Finds.

The cost shows up in Union. To merge x’s group into y’s, we keep one representative, say the one for x, and then go through the whole array to relabel every item that was part of y’s group: