Union-Find
Feb 1, 2022
Complexity
Starting from an empty data structure, path compression (with naive linking) performs any intermixed sequence of m ≥ n find and n — 1 union operations in O(m log n) time. A single find operation is going to take O(log n) time.
References:
