[vseloved]

I examined Union-Find in more detail and found the critical flaw in my description that you were pointing too. Unfortunately, I forgot about it and had a simplified view of this data structure that focused on improving Find but neglected Union. The funny thing is that it was discussed, at times, at group job interviews that I participated as one of the interviewers, and we didn't go these deep to uncover that flaw :) (or, maybe, it was long ago enough for me to forget).

So, I've corrected the Union-Find example to be in line with proper presentation (https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf) removing uf-add in the process. Thanks for the very valuable input.

Surely, that made the example not so bright (as we couldn't reduce everything to a constant-time version with very simple code), but I don't think that the example is inappropriate. It still remains quite simple from the code standpoint. Another reason I picked it was that it didn't require an explanation of any additional data-structure, even, an array, and all the information could be efficiently represented using structs. This still holds.