ConjuntosDisjuntos

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Sets {
    /*
     * This class implements the union-find data structure
     * with union by rank and find with path compression
     */

    private int[] parent;
    private int[] rank;

    public Sets(int n){
        parent = new int[n];
        for(int i=0; i<n; i++) parent[i] = i;
        rank = new int[n];
        for(int i=0; i<n; i++) rank[i] = 0;
    }

    public int find(int v){
        if(v!=parent[v]){
            parent[v] = find(parent[v]);
        }
        return parent[v];
    }

    public void union(int x, int y){
        int xRoot = find(x);
        int yRoot = find(y);
        if(xRoot == yRoot) return;
        if(rank[xRoot] > rank[yRoot]){
            parent[yRoot] = xRoot;
        }
        else{
            parent[xRoot] = yRoot;
            if(rank[xRoot] == rank[yRoot]){
                rank[yRoot]++;
            }
        }
    }

    public void printParent(){
        int[] index = new int[parent.length];
        for(int i=0; i<parent.length; i++) index[i] = i;
        System.out.println("index:  " + Arrays.toString(index));
        System.out.println("parent: " + Arrays.toString(parent));
    }


    public static void main(String[] args) {
        // Part a)
        Sets uf = new Sets(9);
        uf.union(2,1);
        uf.union(4,3);
        uf.union(6,5);
        System.out.println("Parent array after union(2,1), union(4,3) and union(6,5):");
        uf.printParent();

        // Part b)
        uf.union(2, 4);;
        System.out.println("\nParent array after union(2,1)");
        uf.printParent();

        // Part c)
        uf.find(2);
        System.out.println("\nParent array after find(2)");
        uf.printParent();

        // Part d)
        System.out.println("\nDisjoint sets: ");
        HashMap<Integer, HashSet<Integer>> myDict = new HashMap<Integer, HashSet<Integer>>();
        for(int node=0; node<9; node++){
            int root = uf.find(node);
            if(!myDict.containsKey(root)){
                HashSet<Integer> mySet = new HashSet<Integer>();
                mySet.add(node);
                myDict.put(root, mySet);
            }
            else{
                myDict.get(root).add(node);
            }
        }

        for(HashSet<Integer> mySet : myDict.values()){
            System.out.println(mySet);
        }

    }
}