Union Find | Disjoint Sets

Graph.java

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class Graph{
    int V,E;
    Edge edge[];
    class Edge{
        int src,dest;
    }
    Graph(int v, int e){
        E = e;
        V = v;
        edge = new Edge[E];
        for(int i=0;i<e;i++){
            edge[i] = new Edge();
        }
    }
    
    public static void main (String[] args) 
    { 
        /* Let us create following graph 
         0 
        |  \ 
        |    \ 
        1-----2 */
        int V = 3, E = 3; 
        Graph graph = new Graph(V, E); 
        graph.edge[0].src = 0; graph.edge[0].dest = 1; 
        graph.edge[1].src = 1; graph.edge[1].dest = 2; 
        graph.edge[2].src = 0; graph.edge[2].dest = 2; 
  
        if (graph.isCycle(graph)==1) 
            System.out.println( "graph contains cycle" ); 
        else
            System.out.println( "graph doesn't contain cycle" ); 
    } 
    
    int isCycle(Graph g){
        int parent[] = new int[g.V];
        
        //if we are giving rank, give rank here as well
        for(int i=0;i<g.V;++i){
            parent[i] = -1;
        }
        
        for(int i=0;i<g.E;i++){
            int x = g.find(parent,g.edge[i].src);
            int y = g.find(parent,g.edge[i].dest);
            if(x==y) return 1;
            
            g.union(parent,x,y);
        }
        return 0;
    }
    
    int find(int[] parent, int i){
        if(parent[i] == -1) return i;
        return find(parent,parent[i]);
    }
    
    //Path Compression Find
    int findConsideringPathCompression(int[] parent, int i){
        if(parent[i] == -1){
            parent[i] = find(parent,parent[i]);   
        }
        return parent[i];
    }
    
    
    void union(int[] parent, int x, int y){
        int xx = find(parent,x);
        int yy = find(parent,y);
        
        //depending on the rank will decide who will become parent of who
        // if rank equal, make random decision and increase the rank of the one you selected as a parent
        parent[yy]=xx;
    }
}