Disjoint Sets

Two Heuristics:

  1. Union-by-Rank
  2. Path Compression
Funstion Time
CREATE-SET(x) O(1)
UNION(x,y) O(1)
FIND-SET(x) O(m*a(m,n))
#include <iostream>
 
using namespace std;
 
int r[100];
int p[100];
 
void CREATE_SET(int x)
{
    p[x] = x;
    r[x] = 0;
}
 
void UNION(int x, int y)
{
    /* Union-by-rank heuristic */
 
    if(r[x] < r[y])
        p[x] = y;
    else if ( r[x] > r[y])
        p[y] = x;
    else
    {
        p[x] = y;
        r[y] ++;
    }
}
 
int FIND_SET(int x)
{
    int z = x;
    int z1;
 
    while(p[x] != x)
        x = p[x];
 
    /* Path Compression heuristic */
 
    while(p[z] != z)
    {
        z1 = z;
        z = p[z];
        p[z1] = x;
    }
 
    return x;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.