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

• /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;
}
``````

}

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