Disjoint Set Union (DSU)

1. How does it work?
   1. make
   2. find
   3. union
2. Path compression
3. Union by size vs union by rank
4. Time complexity
5. Applications
6. References

Disjoint Set Union (DSU) or is also called Union Find because of its 2 main operations. Problem:

How does it work?

make

find

union

Path compression

Union by size vs union by rank

Time complexity

Applications

• Kruskal

References

1. Disjoint Set Union - CP-Algorithms
2. Competitive Programming 4, section 2.4.2

---