A Disjoint Set (Union-Find) data structure keeps track of elements partitioned into disjoint subsets. It supports union and find operations, and is used in applications like connected components in graphs and Kruskal's algorithm for minimum spanning trees.
Select an operation and enter value(s) to see the explanation here.
| Operation | Without Path Compression | With Path Compression |
|---|---|---|
| Make Set | O(1) | O(1) |
| Find | O(log n) | O(α(n)) |
| Union | O(log n) | O(α(n)) |
Note: α(n) is the inverse Ackermann function, which grows very slowly.