# Interesting applications of union-find

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?