Worst case constructions for DSU?

Правка en2, от shsh, 2025-11-12 09:20:45

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.

Теги dsu

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский shsh 2025-11-12 09:20:45 85
en1 Английский shsh 2025-11-12 08:58:19 334 Initial revision (published)