I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know:
- Kruskal's algorithm for MST
- Tarjan's off-line lowerst common ancestors (LCA) algorithm 1
- Solving range minimum queries using union-find by reduction to LCA (with $O(m+n)$ bound given by [Tarjan & Gabow '83, see 1]
- Finding connected components
- Various textbook examples
Question: What are some interesting use-cases of union-find inside a larger, more complicated algorithm that are lesser-known?
