CODEWITHSUNDEEP
algorithmunion-find
Sobiaholic
Sobiaholic

Reputation: 2957

Union-Find Disjoint+ Path Compression Algorithm

I'm having an exam this sunday and I just want to confirm if what I'm doing is correct ( You know exams make me skeptical)

This is how the algorithm works:

int Find(int x)
{ // Return the set containing x and compress the path from x to root
  // First, find the root
int z = x; while (P[z] > 0) { z = P[z]; } int root = z;
// Start at x again and reset the parent // of every node on the path from x to root z = x;
while (P[z] > 0)
{ int t = P[z];
     P[z] = root; // Reset Parent of z to root
z = t; }
return root; }

This is the question:

Recall the algorithms developed for the Union-Find problem on disjoint sets from a set of n elements. Find uses path compression and Union uses ranking. Also, Union of two trees of the same rank chooses the root associated with 2nd argument as the new root. Start with a set S = {1, 2, ..., 10} and 10 disjoint subsets, each containing a single element. a. Draw the final set of trees after executing:
Union(1,2), Union(3,4), Union(5,6), Union(1,5), Union(1,3).

And this is my solution to the question:

enter image description here

I would love to have any tips or suggestions regarding this Algorithm.

Thanks!

Upvotes: 1

Views: 3732

Answers (1)

coderz
coderz

Reputation: 4989

The key point of Find operation of Union-Find Set is path compression.

If we know the root of set A is r1, and the root of set B is r2, when join set A and set B together. The most simple way is to make set B's root as set A's root, which means father[r2] = r1;

But it is not so "clever", when r2's son, we say x, wants to know its root, x asks its father r2, and then the father r2 asks itself's father r1, blabla, until to the root r1. Next time when asked x's root again, x asks its father r1 "what's our root?", there is not necessary for r1 to repeat the previous loop again. Since r1 already knows its root is r2, r1 can directly return it to x.

In brief, x's root is also x's father's root. So we get how to implement path compression(I think recursion is more straightforward):

int Find(int x)
{
    // initial each element's root as itself, which means father[x] = x;
    // if an element finds its father is itself, means root is found
    if(x == father[x])
        return father[x];
    int temp = father[x];
    // root of x's father is same with root of x's father's root
    father[x] = Find(temp);
    return father[x];
}

It is extremely high performance, about time complexity of path-compressioned find operation, see: http://www.gabrielnivasch.org/fun/inverse-ackermann

Upvotes: 0

Related Questions