[Java] Union Find
Sort the edges in non increasing order as we want to keep the edge with type 3 in the graph and try to remove the edges with type 1 and 2. This is due to we wan
Sort the edges in non increasing order as we want to keep the edge with type 3 in the graph and try to remove the edges with type 1 and 2. This is due to we want to remove maximum number of edges.\n\nThen a simple Union Find separately for Alice and Bob for checking the connectivity of the graph.\n```\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) \n    {\n        Arrays.sort(edges , (a,b) -> b[0] - a[0]);\n        \n        int[] aparent = new int[n+1];\n        int[] bparent = new int[n+1];\n        \n        int[] arank = new int[n+1];\n        int[] brank = new int[n+1];\n        \n        for(int i=0;i<n+1;i++){\n            aparent[i] = i;\n            bparent[i] = i;\n            arank[i] = 1;\n            brank[i] = 1;\n        }\n        \n        int amerged = 1;\n        int bmerged = 1;\n        int remove = 0;\n        \n        for(int[] edge : edges){\n            if(edge[0] == 3){\n                boolean aunion = union(edge[1] , edge[2] , aparent , arank);\n                boolean bunion = union(edge[1] , edge[2] , bparent , brank);\n                \n                if(aunion == true)\n                    amerged++;\n                if(bunion == true)\n                    bmerged++;\n                if(aunion == false && bunion == false)\n                    remove++;\n            }\n            else if(edge[0] == 1){\n                boolean aunion = union(edge[1] , edge[2] , aparent , arank);\n                if(aunion == true)\n                    amerged++;\n                else\n                    remove++;\n            }\n            else{\n                boolean bunion = union(edge[1] , edge[2] , bparent , brank);\n                if(bunion == true)\n                    bmerged++;\n                else\n                    remove++;\n            }\n            \n        }\n        if(amerged != n || bmerged != n)\n                return -1;\n            return remove;\n    }\n    \n    public int find(int x , int[] parent){\n        if(parent[x] == x)\n            return x;\n        int temp = find(parent[x] , parent);\n        parent[x] = temp;\n        return temp;\n    }\n    \n    public boolean union(int x , int y , int[] parent , int[] rank){\n        int lx = find(x , parent);\n        int ly = find(y , parent);\n        \n        if(lx != ly){\n            if(rank[lx] > rank[ly])\n                parent[ly] = lx;\n            else if(rank[ly] > rank[lx])\n                parent[lx] = ly;\n            else{\n                parent[ly] = lx;\n                rank[lx]++;\n            }\n            return true;\n        }\n        return false;\n    }\n}\n```
['Union Find', 'Java']