SAT2020's blog

By SAT2020, history, 2 years ago, In English

Hey everyone,

First off, I'm finally an expert! Thank you to everyone who has responded to my previous blog posts, your input helped me grow as a competitive programmer greatly!

Now, onto the actual question. What is the time complexity of using the "union" and "find" operations with an array-based union-find algorithm? First, let me put some pseudo-code of the union-find algorithm so that my ramblings will make more sense.

// We initialize the array such that each node is its own parent

 array = [0, 1, 2, 3, 4, 5... n]


 // Find the "root" of a node

 function find(index):

      while (array[index] != index)

           index = array[index]

      return index


 // Join the "roots" of two nodes

 function union(a, b):

      array[find(a)] = array[find(b)]

Please someone correct me if my implementation is wrong or if there's any way I can improve my pseudo-code. Now, onto the actual question.

Let's imagine you have a straight, directed graph with randomized node order. For example: 3 --> 5 --> 1 --> 2 --> 4. I speculate that the time complexity of generating the union-find array is at worst O(n^2) and that once the array is generated, the time complexity of finding the root from any given node is at worst O(n). Let's go through the example I provided, assuming that we join nodes starting from the lowest node (1), then the second lowest (2), etc.

Init: [0, 1, 2, 3, 4, 5]

Step 1: [0, 2, 2, 3, 4, 5] // Join 1 and 2

Step 2: [0, 2, 4, 3, 4, 5] // Join 2 and 4

Step 3: [0, 2, 4, 5, 4, 5] // Join 3 and 5

Step 4: [0, 2, 4, 5, 4, 5] // 4 has no outward connections

Step 5: [0, 2, 4, 5, 4, 1] // Join 5 and 1

At this point, if we want to query the third node for its connected component, the complexity will be O(n), because we must traverse the array 3 --> 5 --> 1 -- > 2 --> 4. Furthermore, if every node was connected to every other node, then preprocessing would take O(n^2) complexity!

This is really bad, but union-find is such a popular algorithm, I feel like I must be missing something! What is going on here?

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The union part was wrong. You should set the parent of the component with smaller size to the larger one. This ensure the complexity of find function to be $$$\log{(N)}$$$.

Another way is to do path compression when "climbing up the ancestor".