### code_warrior's blog

By code_warrior, history, 7 months ago,

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!

• 0

 » 7 months ago, # |   0
•  » » 7 months ago, # ^ |   0 Thanks.It helped a lot!
•  » » 7 months ago, # ^ |   0 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!
•  » » » 7 months ago, # ^ |   +8 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.
•  » » » » 7 months ago, # ^ |   0 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?