code_warrior's blog

By code_warrior, history, 7 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.It helped a lot!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?