Disjoint Set Union (DSU) - Preparation to IOI Part 3
Disjoint Set Union (DSU)
Disjoint Set Union (DSU)
Introduction
DSU means Disjoint Set Union. It is also called Union-Find.
The idea is simple: we have many elements, and these elements are split into groups. We want to support two operations quickly:
merge the groups of two elements
check whether two elements are already in the same group
A common example is an undirected graph where edges are added one by one. At the beginning, every vertex is alone. When we add an edge between two vertices, their connected components become one component. When we ask whether two vertices are connected, we only need to know whether they belong to the same component.
By the end of this lecture, students should understand three ideas: the slow coloring solution, the parent-pointer version, and the two optimizations that make DSU very fast.
Problem or motivation
We have n vertices and q operations. At the beginning, there are no edges, so every vertex is a separate component.
There are two types of operations:
1 u v: add an edge between u and v
2 u v: print whether u and v are currently connected
For example, after adding edges (1, 2) and (3, 4), we have two components: {1, 2} and {3, 4}. If we later add edge (2, 3), these two components merge, and now {1, 2, 3, 4} is one component.
This is the kind of situation where DSU is useful: components are merging, and we need to answer connectivity queries quickly.
Naive approach
The most direct idea is to give every component a color.
Let color[i] be the color of the component containing vertex i. At the beginning, every vertex is alone, so every vertex gets a different color:
color[1] = 1
color[2] = 2
color[3] = 3
and so on
To check whether u and v are connected, we compare their colors. If color[u] == color[v], they are in the same component. Otherwise, they are in different components.
The problem appears when we add an edge. Suppose we want to merge the component of u with the component of v. If their colors are different, then all vertices with one color must be recolored into the other color.
For example:
color = [1, 1, 3, 3, 5, 6]
Here vertices 1 and 2 are together, vertices 3 and 4 are together, and vertices 5 and 6 are alone. If we add edge (2, 3), then the components of 2 and 3 must merge. We can change every color 1 into color 3:
color = [3, 3, 3, 3, 5, 6]
The update is easy to understand, but it scans the whole array.
This solution is correct, because equal colors mean equal components. But one merge can take O(n) time. If there are many operations, this becomes too slow.
Rewritten Naive
The slow part of the coloring solution is that a merge updates many vertices immediately. DSU starts by changing this idea.
Instead of storing the final color for every vertex, we store a parent pointer. Each component is represented as a tree. The root of the tree is the representative of the component. If parent[x] = x, then x is the root.
To know which component contains x, we follow parent pointers until we reach the root. This operation is called find_set(x).
To merge two components, we find their roots. If the roots are different, we make one root point to the other root. This joins two trees into one tree.
This already feels better than recoloring. A merge no longer scans all vertices. It only changes one pointer: the root of one component starts pointing to the root of the other component.
But this version can still be bad. If we always attach roots carelessly, we may create a long chain:
1 -> 2 -> 3 -> 4 -> 5
Then find_set(1) must walk through the whole chain. So in the worst case, find_set can still take O(n) time.
Making it faster with size
To avoid long chains, we store the size of each component.
Let size[root] be the number of vertices in the component whose root is root. When we merge two components, we attach the smaller tree under the larger tree. This idea is often called union by size. It is also the same small-to-large idea: when something must be attached, attach the smaller object to the bigger object.
After find_set, both X and Y are roots. If size[X] > size[Y], we swap them. After that, X is the smaller root and Y is the larger root. So we attach X under Y and increase size[Y].
One important detail: size[x] is meaningful only when x is a root. If x is not a root, we do not use its size.
Why does this give O(logn) per operation? Look at one vertex. Its depth increases only when the whole tree containing it is attached under another tree. But we attach a tree only under a tree of at least the same size. So whenever the depth of a vertex increases by 1, the size of its component at least doubles.
A component containing this vertex can grow like this:
1 -> 2 -> 4 -> 8 -> 16 -> ...
It cannot double more than logn times before it becomes larger than n. Therefore, the depth of any vertex is at most O(logn). This means find_set takes O(logn) time when we use union by size.
Path compression
Union by size already makes the trees short. Path compression makes them even shorter.
When find_set(x) walks from x to the root, it discovers the representative of the whole path. After we know the representative, we can make x point directly to it.
For example, suppose the path is:
7 -> 4 -> 2 -> 1
The root is 1. After calling find_set(7), the vertices on this path can point directly to 1. Future calls become much faster.
This one assignment is very important:
parent[x] = find_set(parent[x])
It says: first find the real root, then remember it as the direct parent of x.
Core concept and main algorithm
The final DSU represents every component as a rooted tree. The root is the representative of the component.
We maintain two arrays:
parent[x]: where x points in the DSU tree
size[x]: the component size, meaningful only for roots
The main rule is simple: two vertices are in the same component if and only if their representatives are the same.
Algorithm:
The big improvement is that we do not update every vertex during a merge. We only connect two roots. Then find_set uses parent pointers to discover the current representative.
Mental model and detailed walkthrough
Think of DSU as two pictures that move together.
The original graph stores the real edges we added.
The DSU forest stores only parent pointers used by the data structure.
These are not the same thing. The original graph may contain many edges inside one component, but the DSU only needs enough parent pointers to know the representative.
Now let us walk through a full small example. We will only add edges here, because this visual is about how the DSU tree is built:
add edge (1, 2)
add edge (3, 4)
add edge (2, 3)
add edge (5, 6)
add edge (4, 6)
In the trace below, the top visual is the original graph and the bottom visual is the DSU forest. The DSU forest is drawn in a rooted way, so it is easy to see who is the current root of each component.
The most important thing to notice is this: the top graph stores all added edges, but the bottom DSU forest stores only enough information to answer connectivity quickly. That is why the DSU tree does not look the same as the original graph.
Implementation
This implementation solves the dynamic connectivity problem from the motivation section.
Input format:
first line: n q
next q lines: type u v
type = 1 means add an edge between u and v
type = 2 means ask whether u and v are connected
Complexity
Initialization:O(n).
With only union by size: each operation takes O(logn) in the worst case.
With union by size and path compression: operations are almost O(1) in practice, more precisely O(α(n)) amortized.
Memory:O(n).
1. Initialize the DSU.
1. For every vertex x from 1 to n:
1. parent[x] = x
2. size[x] = 1
2. To find the representative of x:
1. If parent[x] = x, return x.
2. Otherwise, find the representative of parent[x].
3. Save that representative into parent[x].
4. Return parent[x].
3. To merge the components of x and y:
1. X = find_set(x)
2. Y = find_set(y)
3. If X = Y, stop. They are already in the same component.
4. If size[X] > size[Y], swap X and Y.
5. Make parent[X] = Y.
6. Add size[X] to size[Y].
4. To check whether x and y are connected:
1. Return whether find_set(x) = find_set(y).
void unite_naive(int u, int v){ int old_color = color[u]; int new_color = color[v]; if(old_color == new_color){ return;} for(int i = 1; i <= n; i++){ if(color[i] == old_color){ color[i] = new_color;}}}
struct DSU{ vector<int> parent; DSU(int n) : parent(n + 1, -1){} void make_set(int x){ parent[x] = x;} int find_set(int x){ if(parent[x] == x){ return x;} return find_set(parent[x]);} void union_sets(int x, int y){ int X = find_set(x); int Y = find_set(y); if(X != Y){ parent[X] = Y;}}};
