Union-find

Union-find: how it works

In this tool: disjoint sets, path compression. Put in your own values and watch it change. Each operation runs one step at a time and says in plain words what happened, with its calculation worked out. The code is shown in Python, C, C++ or Java with the line that just ran marked, and an Understand it panel gives the idea, why it works, the cost of each operation, common mistakes and a short quiz.

Lessons that use it

• Disjoint sets (union-find) (Data Structures)Keep track of which items are in the same group, merging groups in almost constant time with union by size and path compression.