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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy