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 | tourist | 3851 |

2 | jiangly | 3634 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | ksun48 | 3493 |

6 | djq_cpp | 3486 |

7 | maroonrk | 3471 |

8 | Radewoosh | 3442 |

9 | Petr | 3426 |

10 | Isonan | 3344 |

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

1 | -is-this-fft- | 185 |

2 | awoo | 180 |

3 | dario2994 | 172 |

4 | Um_nik | 168 |

4 | maroonrk | 168 |

4 | adamant | 168 |

7 | SecondThread | 167 |

8 | YouKn0wWho | 166 |

8 | errorgorn | 166 |

10 | Monogon | 164 |

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-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/24/2022 22:55:37 (h3).

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