Disjoint Set Union
Works in time.
- Always connect the representative of the smaller set to the representative of the larger set (or if the sets are of equal size, we can make an arbitrary choice).
Implementation
link
contains for each element the next element in the chain or the element itself if it is a representativesize
indicates for each representative the size of the corresponding set
for (int i = 1; i <= n; i++) link[i] = i;
for (int i = 1; i <= n; i++) size[i] = 1;
int find(int x) {
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
bool same(int a, int b) {
return find(a) == find(b);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (size[a] > size[b]) swap(a,b); // Connect the smaller set to the bigger set
size[b] += size[a];
link[a] = b;
}
Optimizations
Path Compression Optimization
The find
function is naive and can take . We can optimize it so every time you call find, you update the parent directly to the root.
int find(int x) { // Naive
while (x != link[x]) x = link[x];
return x;
}
int find(int x) { // Optimized
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
This allows us to achieve on average.
2. Union by size (already implemented) in the logic above
Applications
- Kruskal’s Algorithm for finding the Minimum Spanning Tree