Disjoint Set Union Problems
Union–find answers "are these two in the same group?" in near-constant time. These problems start with counting components and build up to tracking leaders and merging whole ranges. Tick off the ones you solve; your progress is saved in this browser.
-
1
n students and m pairs who share a religion. Find the largest possible number of distinct religions, i.e. the number of components.
-
2
Support 3 operations:
- Merge the group of soldier a into the group of soldier b
- Make soldier a the leader of their group
- Print the leader of soldier a's group
-
3
Split n distinct numbers into sets A and B so that x ∈ A implies a − x ∈ A, and x ∈ B implies b − x ∈ B.
-
4
Support 3 operations:
- Merge the departments of employees x and y
- Merge the departments of every employee from x to y
- Check whether x and y are in the same department
-
5
From a Codeforces group contest; you need to join the group to open it.
-
6
From a Codeforces group contest; you need to join the group to open it.
No problems match. Clear filters
Frequently asked questions
What is a disjoint set union (union–find) data structure?
Disjoint set union keeps a collection of non-overlapping sets as a forest, where each tree’s root is the set’s representative. find(x) returns x’s root and union(a, b) links two roots, so you can merge groups and ask whether two elements are in the same group.
What is the time complexity of union–find?
With both path compression and union by rank (or size), any sequence of m operations on n elements runs in O(m · α(n)) time, where α is the inverse Ackermann function. α(n) is at most 4 for any practical n, so each operation is effectively constant time.
When should I use DSU instead of BFS or DFS?
Use DSU when edges arrive over time and you repeatedly ask whether two nodes are connected, or when you need to merge groups (for example in Kruskal’s minimum spanning tree). BFS/DFS is simpler when the graph is fixed and you only need to explore it once.