Disjoint Set Union

Implementation of Disjoin set union.

Example 1:

Input : n=5 , union(1,2), union(3,4), find(1),union(3,5), find(5)
Output: 1 3

Approach 1: Naive approach

Java

public class DisjointSetUnion {
    // parent array
    static int parent[];

    public static void main(String[] args) {
        int n = 5;
        // initialization of no of parent
        parent = new int[n + 1];
        make_set(n);

        // Combine the set in which
        // 1 and 2 occur
        union_sets(1, 2);
        // Combine the set in which
        // 3 and 4 occur
        union_sets(3, 4);

        // find set in which 1
        // is present
        System.out.print(find_set(1) + " ");

        // union of 3 and 5
        union_sets(3, 5);
        // find the set in which 5
        // is present
        System.out.print(find_set(5) + " ");
    }

//function to make the set
//of each element as itself
//as their parent
    static void make_set(int n) {
        for (int i = 1; i <= n; i++)
            parent[i] = i;
    }

//find the set in which 
//the given node is
//present
    static int find_set(int v) {
        if (v == parent[v])
            return v;
        return find_set(parent[v]);
    }

//function to union 
//of two sets in which a
//and b present
    static void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b)
            parent[b] = a;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;
int parent[10001];

//function to make the set
//of each element as itself
//as thier parent
void make_set(int n)
{
    for(int i=1;i<=n;i++)
        parent[i]=i;
}

//find the set in which 
//the given node is
//present
int find_set(int v)
{
    if(v==parent[v])
        return v;
    return find_set(parent[v]);
}


//function to union 
//of two sets in which a
//and b present
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
       parent[b]=a;
}
int main()
{
  int n=5;
  make_set(n);

  //combibe the set in which
  //1 and 2 occur
  union_sets(1,2);
  //combibe the set in which
  //3 and 4 occur
  union_sets(3,4);

  //find set in which 1
  //is prenent
  cout<<find_set(1)<<"\n";

  //union of 3 and 5
  union_sets(3,5);
  //find the set in which 5
  //is present
  cout<<find_set(5)<<"\n";

}

Approach 2: Path Compression

Java

public class DisjointSetUnion {
    // parent array
    static int parent[];

    public static void main(String[] args) {
        int n = 5;
        // initialization of no of parent
        parent = new int[n + 1];
        make_set(n);

        // Combine the set in which
        // 1 and 2 occur
        union_sets(1, 2);
        // Combine the set in which
        // 3 and 4 occur
        union_sets(3, 4);

        // find set in which 1
        // is present
        System.out.print(find_set(1) + " ");

        // union of 3 and 5
        union_sets(3, 5);
        // find the set in which 5
        // is present
        System.out.print(find_set(5) + " ");
    }

//function to make the set
//of each element as itself
//as their parent
    static void make_set(int n) {
        for (int i = 1; i <= n; i++)
            parent[i] = i;
    }

//find the set in which 
//the given node is
//present
    static int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v]=find_set(parent[v]);
    }

//function to union 
//of two sets in which a
//and b present
    static void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b)
            parent[b] = a;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;
int parent[10001];

//function to make the set
//of each element as itself
//as thier parent
void make_set(int n)
{
    for(int i=1;i<=n;i++)
        parent[i]=i;
}

//find the set in which 
//the given node is
//present
int find_set(int v)
{
    if(v==parent[v])
        return v;
    return  parent[v]= find_set(parent[v]);
}


//function to union 
//of two sets in which a
//and b present
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
       parent[b]=a;
}
int main()
{
  int n=5;
  make_set(n);

  //combibe the set in which
  //1 and 2 occur
  union_sets(1,2);
  //combibe the set in which
  //3 and 4 occur
  union_sets(3,4);

  //find set in which 1
  //is prenent
  cout<<find_set(1)<<"\n";

  //union of 3 and 5
  union_sets(3,5);
  //find the set in which 5
  //is present
  cout<<find_set(5)<<"\n";

}

Approach 3: Union by size

Java

public class DisjointSetUnion {
    // parent array
    static int parent[];
    static int size[];

    public static void main(String[] args) {
        int n = 5;
        // initialization of no of parent
        parent = new int[n + 1];
        size = new int[n + 1];
        make_set(n);

        // Combine the set in which
        // 1 and 2 occur
        union_sets(1, 2);
        // Combine the set in which
        // 3 and 4 occur
        union_sets(3, 4);

        // find set in which 1
        // is present
        System.out.print(find_set(1) + " ");

        // union of 3 and 5
        union_sets(3, 5);
        // find the set in which 5
        // is present
        System.out.print(find_set(5) + " ");
    }

//function to make the set
//of each element as itself
//as their parent
    static void make_set(int n) {
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

//find the set in which 
//the given node is
//present
    static int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

//function to union 
//of two sets in which a
//and b present
    static void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }

            parent[b] = a;
            size[a] += size[b];
        }

    }
}

C++

#include <bits/stdc++.h>
using namespace std;
int parent[10001];
int size1[10001];
//function to make the set
//of each element as itself
//as thier parent
void make_set(int n)
{
    for(int i=1;i<=n;i++)
        {
            parent[i]=i;
            size1[i]=1;
        }
}

//find the set in which 
//the given node is
//present
int find_set(int v)
{
    if(v==parent[v])
        return v;
    return  parent[v]= find_set(parent[v]);
}


//function to union 
//of two sets in which a
//and b present
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
       {
           if(size1[a]<size1[b])
             swap(a,b);
            
           parent[b]=a;
           size1[a]+=size1[b];
       }
}
int main()
{
  int n=5;
  make_set(n);

  //combibe the set in which
  //1 and 2 occur
  union_sets(1,2);
  //combibe the set in which
  //3 and 4 occur
  union_sets(3,4);

  //find set in which 1
  //is prenent
  cout<<find_set(1)<<"\n";

  //union of 3 and 5
  union_sets(3,5);
  //find the set in which 5
  //is present
  cout<<find_set(5)<<"\n";

}