Q37 Redundant Connection - LeetCode 684
Mon Jun 12 2023 09:22:37 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
int parent[];
int size[];
int ans[] ;
public int findparent(int u){
if(parent[u] == u)
return u;
return parent[u] = findparent(parent[u]);
}
public void union(int x , int y ){
int lx = findparent(x);
int ly = findparent(y);
if(lx != ly){
if(size[lx] > size[ly]){
parent[ly] = lx;
}
else{
parent[lx] = ly;
if(size[lx] == size[ly])
size[lx]++;
}
}
/* if already parents are equal means there already exist a path between nodes
that means this edge is generating a cycle in the graph
*/
else{
ans[0] = x;
ans[1] = y;
}
}
public int[] findRedundantConnection(int[][] edges) {
/* Q37 graph playlist , the extra edge is creating a cycle therefore we find
the last edge which is creating a cycle using DSU
1) we merge nodes
2) if parents of 2 nodes to merged are equal in union means they are creating a
cycle so update answer ,
*/
int m = edges.length , n = edges[0].length ;
ans = new int[2];
parent = new int[m+1];
size = new int[m+1];
//initialising DSU
for(int i = 0 ; i < m ; i++){
parent[i] = i;
size[i] = 1;
}
//merging
for(int edge[] : edges){
int a = edge[0] , b = edge[1];
union(a , b);
}
return ans;
}
}
content_copyCOPY
https://leetcode.com/problems/redundant-connection/description/
Comments