class Solution { public int[] findRedundantDirectedConnection(int[][] edges) { /*Q38 DSU concept , there can be 3 cases , indegree = 2 , cycle or indegree =2+cycle we will handle this using DSU concept */ int n = edges.length; //write DSU find and union and initialize parent and size parent = new int[n+1] ; //as not 0 based indexing size = new int[n+1]; for(int i = 0;i < n+1 ; i++){ parent[i] = i; size[i] = 1; } int indegree[] = new int[n+1]; //as n edges Arrays.fill(indegree , -1); //finding indegree and blacklist edges int black1 = -1 , black2 = -1; for(int i = 0 ; i < n ; i++){ int u = edges[i][0] , v = edges[i][1]; //coming the first time if(indegree[v] == -1){ indegree[v] = i; //marking indegree with row of edges } //making indegree 2 else{ //marking 2 blacklist black1 = i; black2 = indegree[v]; break; //indegree 2 } } //now handling for all 3 cases for(int i = 0 ; i < n ; i++){ //assuming blacklisted1 is the answer if(i == black1) continue; int u = edges[i][0] , v = edges[i][1]; //cyle is present -> case 2 or case 3 if(union(u,v) == true){ if(black1 == -1) //case 2 return edges[i]; else //case 3 return edges[black2]; } } //if cycle is not present its case 1 or case 3 return edges[black1]; } int parent[]; int size[]; public int findparent(int u){ if(parent[u] == u) return u; return parent[u] = findparent(parent[u]); } public boolean 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[ly] ++; } return false; } return true; //cycle detected } }