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

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | adamant | 177 |

2 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 155 |

8 | ko_osaga | 151 |

8 | dario2994 | 151 |

10 | SecondThread | 149 |

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

I want

Unable to figure out a way to do this optimally.

DSU I am using is on cp-algorithms

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 07:52:33 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

On the cp-algorithms page there is an example of this under the title "Storing the DSU explicitly in a set list".

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.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)

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:

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:

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.

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.I think you mean this:

You can check how this code works in EDU : DSU, pretty useful. Hope i helped