What sequences of union/find queries will achieve the worst case complexity of a DSU? I'm specifically interested in a DSU with path compression but **without** union by rank/size, which has worst case complexity $\mathcal{O}(m \log n + n)$, but constructions for other variations are welcome as well.↵
↵
A nice proof for the $\mathcal{O}(m \log n + n)$ bound would also be appreciated.
↵
A nice proof for the $\mathcal{O}(m \log n + n)$ bound would also be appreciated.
