I have recently read tutorial on dsu on trees in codeforces (Arpa's Blog).See this blog.(Specifically,the one titled easy to code in O(nlogn))I couldn't understand how the time complexity of it is O(nlogn).Please ,someone explain me!

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

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

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

1 | Errichto | 202 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

I have recently read tutorial on dsu on trees in codeforces (Arpa's Blog).See this blog.(Specifically,the one titled easy to code in O(nlogn))I couldn't understand how the time complexity of it is O(nlogn).Please ,someone explain me!

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2021 01:57:21 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

...

Thanks.It helped a lot!

But , one thing which I couldn't understand is that when we make the vector pointer point to the vector pointer corresponding to the largest set, is that taking O(n) time or O(1) time!

It's $$$O(1)$$$. Pointer is just a number that shows where the real vector is in the computer's memory. No data is being copied.

Ok,so we are copying all the elements of the vector except the elements corresponding to the largest vector(by size) and perhaps that's why the time complexity of merging sets is O(nlogn) instead of O(n*n). Am i right?