Complete Guide on DSU/ Union Find

If you’ve spent any time solving graph problems in competitive programming, you’ve probably encountered situations where you need to quickly determine whether two elements belong to the same group. Doing this efficiently can be the difference between passing and timing out. That’s where Union-Find, also known as Disjoint Set Union (DSU), comes in.

What is Union-Find?

Union-Find is a data structure used to manage a collection of disjoint (non-overlapping) sets. It supports two primary operations:

1. Find(x): Determines which set an element belongs to
2. Union(x, y): Merges the sets containing x and y

Why is it Important?

In competitive programming, performance is critical. Union-Find allows near constant-time operations, making it ideal for handling large inputs efficiently.

Core Idea:

Each set is represented as a tree, where each node points to a parent and the root node acts as the representative of the set.

Find with Path Compression:

int find(int x) {

if (parent[x] == x)

return x;

return parent[x] = find(parent[x]);

}

Union by Rank:

void unionSet(int a, int b) {

int pa = find(a), pb = find(b);

if (pa == pb) return;

if (rank[pa]< rank[pb])

parent[pa] = pb;

else if ((rank[pb] < rank[pa])

parent[pb] = pa;

else {

parent[pb] = pa;

rank[pa]++;

}

}

Applications:

1. Cycle detection in graphs

2. Kruskal’s algorithm (Minimum Spanning Tree)

3. Connected components

4. Dynamic connectivity problems

5. Grid-based problems like number of islands

Conclusion:

Union-Find is a powerful and essential tool in competitive programming. Mastering it will significantly improve your efficiency in solving graph-related problems and give you an edge in contests.