skpro19's blog

Question regarding time complexity
By skpro19, history, 7 years ago, In English

I am solving this DIV 2C. This is my submission which got accepted.

My question is this:

Why isn't updating the parent of a node, an O(n) operation ?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You are constructing the disjoint set using path compression. i.e. When you look for the father of a node, each node on the path to the root remember the father, so the complexity is not linear per query. If you want to be even more sure about the complexity you should do rank compression, i.e. remember for each tree their height, and make the shorter tree child of the taller tree (the one with highest height). The overall complexity per query is ackerman inverse per query (amortized).

More info about Disjoint Set.

→ Reply