Q28 Remove Max Number of Edges to Keep Graph Fully Traversable - LeetCode 1579

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        /* as its kind of a dynamic graph we use DSU 
        */
        
        //giving common edges top priority that is of type 3
        Arrays.sort(edges , (a,b)-> b[0] - a[0]);
        
        //alice nodes=1 as for 1st merge 2 nodes get connected to each other
        int removed_edge = 0, alice_nodes = 1, bob_nodes = 1;

        DSU alice = new DSU(n+1);   //1 based indexing
        DSU bob = new DSU(n+1);

        for(int edge[] : edges){
            
            //taking out edges
            int a = edge[1] , b = edge[2];

            //giving common edges top priority
            if(edge[0] == 3){
                
                //if leaders of a and b are not same they will get merged 
                if(alice.union(a , b , alice.parent , alice.rank)){
                    bob.union(a , b , bob.parent , bob.rank);
                    alice_nodes++;
                    bob_nodes ++;
                }
                //if leaders are same that edge can be removed
                else
                removed_edge++;
                
            }
            else if(edge[0] == 2){
                if(bob.union(a , b , bob.parent , bob.rank))
                bob_nodes ++;
                
                else
                removed_edge++;
            }
            else{
                if(alice.union(a , b , alice.parent , alice.rank))
                alice_nodes ++;
                
                else
                removed_edge++;
            }
        }

        if(alice_nodes != n || bob_nodes != n)
        return -1;

        return removed_edge;
    }

    public class DSU{
        int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){
                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }
}