Union-Find (disjoint set)
mediumEither optimisation alone gives O(log n); together they give the inverse Ackermann function, which stays below 5 for any input you will ever have. Watch a long chain flatten on its first query.
Average
O(α(n)) ≈ O(1)Worst O(log n) without both optimisationsSpace O(n)Loading the union-find (disjoint set) engine…