DSU Magic

Revision ru1, by muzzaleeni, 2020-02-27 13:54:19

It turns out, that the final amortized time complexity is $$$O(α(n))$$$, where $$$α(n)$$$ is the inverse Ackermann function, which grows very slowly. In fact it grows so slowly, that it doesn't exceed $$$4$$$ for all reasonable $$$n$$$ (approximately $$$n<10^{600})$$$.

code

Question: Why this works in $$$O(α(n))$$$?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian muzzaleeni 2020-02-27 13:54:19 473 Первая редакция перевода на Русский
en1 English muzzaleeni 2020-02-27 13:53:01 471 Initial revision (published)