### bloodoath's blog

By bloodoath, history, 9 months ago,

Given, two disjoint sets with roots 1 and 6 respectively which already have their childrens' paths compressed.

I wish to do a union but instead of

this

I want

this

Unable to figure out a way to do this optimally.

DSU I am using is on cp-algorithms

• 0

 » 9 months ago, # |   0 On the cp-algorithms page there is an example of this under the title "Storing the DSU explicitly in a set list".
•  » » 9 months ago, # ^ |   0 It will also return the first form and it still requires me to run a recursive find_set once to achieve the second form from the first, which will give me O(n^2) in the worst case. I guess there is no way, I should probably give it up for now. Thanks for your comment.
•  » » » 9 months ago, # ^ |   0 Why should it? Let's do the following.We maintain the invariant that after any merge operation, every single component is a star graph (I hope that is what you meant).Let's maintain the sizes of every component in a array called sz, and for each "representative", a vector of all the vertexes that belong to him (let it be g). Now, we use the small-to-large technique — when we merge components with representative P_a and representative P_b, (|P_a| > |P_b|), we simply iterate over all vertexes in g[P_b], add them to g[P_a], increase the size of P_a by |P_b|, and directly link them, thus maintaining the invariant. As every time a vertex gets redirected, the size increases at least two times, each vertex will be merged no more than O(NlogN) times, and we get a runtime ofO(NlogN + Q)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 I'm not sure what you mean, you can directly create the graph you wanted from the lst array?The first picture would have two non-empty entries in lst: lst[1] = [1,2,3,4] lst[6] = [6, 5, 8, 7] You then merge any node in lst[1] with any node in lst[6] and you'll end up with one item in the list: lst[1] = [1,2,3,4,5,6,7,8]. Every node will also have parent[x] = 1.It looks like the worst case complexity is bad but small to large merging ensures that it isn't O(n^2) as each item would only be moved at most log n times.
•  » » » 9 months ago, # ^ |   +19 Thank you induk_v_tsiane and robostac for the explanation. I didn't notice the fact that each item doesn't get moved more than log(n) times.
 » 9 months ago, # | ← Rev. 2 →   0 I think you mean this: int get(int a){ if (a != p[a]){ p[a] = get(p[a]); } return p[a]; } void unio(int a, int b){ a = get(a); b = get(b); if (a != b){ if (s[a] > s[b]) swap(a, b); p[a] = b; s[b] += s[a]; } } You can check how this code works in EDU : DSU, pretty useful. Hope i helped