3 ms·

Can you give some examples where union-find is applied to great benefit?

• superjan 4y ago
  One example is connected component analyis on images. In one linear scan of an image (2d or 3d) you can find all connected blobs in an image.
• fumblebee 4y ago
  A while back I had to perform an entity resolution task on several million entities. We arrived at a point in the algorithm where we had a long list of connected components by ids that needed to be reduced into a mutually independent set of components, e.g. ({112, 531, 25}, {25, 238, 39, 901}, {43, 111}, ...) After much head banging about working out way to do this that wouldn't lead to an out-of-memory error, we found the Disjoint Set Forest Data Structure and our prayers were answered. I was very grateful for it!
  • BeetleB 4y ago
    Exactly the same for me. We had a defect management system, and a defect can be connected to others as dupes. We'd have whole chains of dupes. We used union find to identify them.
• jobigoud 4y ago
  I used it to find and track islands of connected polygons in 3D meshes.
• clashmeifyoucan 4y ago
  a textbook example of an algorithm that works very well with union-find is the kruskal's algorithm to find the minimum weight spanning tree given a graph. Using union-find improves the time complexity of the algorithm from O(V²) to O(ElogV). This happens because kruskal's algorithm essentially selects the cheapest edge not already included in our spanning tree that won't cause a cycle. So union-find is able to speed up this potential cycle check which would otherwise be naively quadratic.