Java Program to Implement Disjoint Set Data Structure

Code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class DisjointSets 
{
    private List

    public DisjointSets()
    {
        disjointSet = new ArrayList
    }

    public void create_set(int element)
    {
        Map> map = new HashMap>();
        Set set = new HashSet();
        set.add(element);
        map.put(element, set);
        disjointSet.add(map);
    }

    public void union(int first, int second)
    {
        int first_rep = find_set(first);
        int second_rep = find_set(second);

        Set first_set = null;
        Set second_set = null;

        for (int index = 0; index < disjointSet.size(); index++)
        {
            Map> map = disjointSet.get(index);
            if (map.containsKey(first_rep))
            {
                first_set = map.get(first_rep);
            } else if (map.containsKey(second_rep))
            { 
                second_set = map.get(second_rep);
            }
        }

        if (first_set != null && second_set != null)
        first_set.addAll(second_set);

        for (int index = 0; index < disjointSet.size(); index++)
        {
            Map> map = disjointSet.get(index);
            if (map.containsKey(first_rep))
            {
                map.put(first_rep, first_set);
            } else if (map.containsKey(second_rep))
            {
                map.remove(second_rep);
                disjointSet.remove(index);
            }
        }

        return;
    }

    public int find_set(int element)
    {
        for (int index = 0; index < disjointSet.size(); index++)
        {
            Map> map = disjointSet.get(index);
            Set keySet = map.keySet();
            for (Integer key : keySet)
            {
                Set set = map.get(key);
                if (set.contains(element))
                {
                    return key;
                }
            }
        }
        return -1;
    }

    public int getNumberofDisjointSets()
    {
        return disjointSet.size();
    }

    public static void main(String... arg)
    {
        DisjointSets disjointSet = new DisjointSets();

        for (int i = 1; i <= 5; i++)
        {
            disjointSet.create_set(i);
        }

        System.out.println("ELEMENT : REPRESENTATIVE KEY");
        for (int i = 1; i <= 5; i++)
        {
            System.out.println(i + "\t:\t" + disjointSet.find_set(i));
        } 

        disjointSet.union(1, 5);
        disjointSet.union(5, 3);

        System.out.println("\nThe Representative keys after performing the union operation\n");
        System.out.println("Union of (1 and 5)  and (5 and 3) ");

        System.out.println("ELEMENT : REPRESENTATIVE KEY");
        for (int i = 1; i <= 5; i++)
        {
            System.out.println(i + "\t:\t" + disjointSet.find_set(i));
        }

        System.out.println("\nThe number of disjoint set : "+ disjointSet.getNumberofDisjointSets());
    }
}


Output:

ELEMENT : REPRESENTATIVE KEY
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5

The Representative keys after performing the union operation

Union of (1 and 5)  and (5 and 3) 
ELEMENT : REPRESENTATIVE KEY
1 : 1
2 : 2
3 : 1
4 : 4
5 : 1

The number of disjoint set : 3


More Java Programs: