DSU - incorrect application of union by size to other problems?

Author: michalburger1Created Aug 5, 2026Updated Aug 5, 2026

In the DSU article there's a section that reads:

This idea of adding the smaller part to a bigger part can also be used in a lot of solutions that have nothing to do with DSU.

And then proceeds to show how in a tree structure we can add smaller subsets to larger subsets and end up with logarithmic complexity.

Now maybe I'm misunderstanding something, but I believe that the argument "each number will only be added to a set at most O(log n) times" only holds if the two sets we merge are disjoint, i.e. the resulting set increases in size by the number of items we've added. But in this case, we're merging non-disjoint sets so the resulting set may not increase in size at all and the complexity analysis doesn't hold anymore.

Now I don't know if the quoted complexity is still correct or not, but it should be eiter better explained if it is, or completely removed if it isn't.

Source: cp-algorithms/cp-algorithms