Q38 Redundant Connection II - LeetCode 685

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
    }
}