Java Union Find Solution, Simply Explained; Beats 100%.


  • 0
    S

    /Approach:
    Using Union-Find Algo, find if the two vertices are in a common set. If so then it's a cycle.
    How Union-Find works: Each vertex in the edges array is a disjoint set initially. When we start traversing through
    the array, we'll check whether both the vertices of an edge are present within a common set. If both vertices are in different set then perform the union of the sets. If the vertices are present in the same set, then we've found a cycle.
    /

    class Solution {
    public int[] findRedundantConnection(int[][] edges) {

        int[] parent = new int[2000]; //create an array of the size>= max value of an integer in 2D array
        for(int i=0;i<parent.length;i++){
            parent[i] = -1;
        }
        for(int i=0;i<edges.length;i++){
            int x = find(parent, edges[i][0]);
            int y = find(parent,edges[i][1]);
            if(x==y){
                return new int[]{edges[i][0],edges[i][1]};
            }
            union(parent,x,y);
        }
        return new int[0];
    }
    
    public int find(int[] parent, int i){
        if(parent[i]==-1){
            return i;
        }
        return find(parent, parent[i]);
    }
    
    public void union(int[] parent, int x, int y){
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset]  = yset;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.