Easy Java Solution | DSU | Union Find | Beats 100 💯✅
Max Number of Edges to Remove\n\n## Problem Statement\n\nGiven an undirected graph with n nodes and a list of edges, where each edge is of one of three types:\n
# Max Number of Edges to Remove\n\n## Problem Statement\n\nGiven an undirected graph with `n` nodes and a list of `edges`, where each edge is of one of three types:\n\n- Type 1: Can be traversed by Alice.\n- Type 2: Can be traversed by Bob.\n- Type 3: Can be traversed by both Alice and Bob.\n\nOur goal is to remove the maximum number of edges such that both Alice and Bob can still traverse all nodes. If it\'s not possible to do so, return `-1`.\n\n## Intuition\n\nTo solve this problem, we need to ensure both Alice and Bob can traverse all the nodes in the graph using the fewest edges possible. The type 3 edges are the most valuable since they can be used by both Alice and Bob. By prioritizing these edges, we can potentially minimize the number of edges needed for both Alice and Bob.\n\nThe key steps are:\n1. Use type 3 edges first to build a common structure for both Alice and Bob.\n2. Then, use type 1 edges to connect Alice\'s graph.\n3. Lastly, use type 2 edges to connect Bob\'s graph.\n4. Check if both Alice and Bob can traverse all nodes. If not, return `-1`.\n\n## Approach\n\n1. **Union-Find Initialization:** We use a Union-Find data structure to manage the connectivity of nodes for both Alice and Bob.\n\n2. **Sort and Process Edges:** \n    - Sort the edges based on type in descending order so that type 3 edges come first.\n    - Iterate through the sorted edges:\n      - For type 3 edges, try to connect the nodes for both Alice and Bob.\n      - For type 1 edges, try to connect the nodes for Alice only.\n      - For type 2 edges, try to connect the nodes for Bob only.\n    - Count the number of edges added to the Union-Find structures.\n\n3. **Connectivity Check:** After processing all edges, check if both Alice and Bob\'s Union-Find structures have only one connected component each. If either does not, return `-1`.\n\n4. **Calculate Result:** The result is the total number of edges minus the number of edges used.\n\n## Complexity Analysis\n\n- **Time Complexity:** The algorithm mainly involves sorting the edges and performing union-find operations. Sorting takes `O(E log E)`, where `E` is the number of edges. Each union or find operation is nearly constant time, amortized to `O(alpha(N))`, where `(alpha)` is the inverse Ackermann function. Thus, the total time complexity is `(O(E log E + E alpha(N))`, which is `(O(E log E)` since `(alpha(N))` is very slow-growing.\n\n- **Space Complexity:** The space complexity is `(O(N + E))`, where `(N)` is the number of nodes and `(E)` is the number of edges. This includes the space for the Union-Find structures and the edges list.\n\n\n# Code\n```\nclass Solution {\n    class UnionFind {\n        int[] parent;\n        int[] rank;\n        int count;\n        public UnionFind(int n) {\n            parent = new int[n];\n            rank = new int[n];\n            count = n;\n            for (int i = 0; i < n; i++) {\n                parent[i] = i;\n                rank[i] = 0;\n            }\n        }\n\n        public int find(int x) {\n            if (parent[x] != x) {\n                parent[x] = find(parent[x]);\n            }\n            return parent[x];\n        }\n\n        public boolean union(int x, int y) {\n            int rootX = find(x);\n            int rootY = find(y);\n\n            if (rootX != rootY) {\n                if (rank[rootX] > rank[rootY]) {\n                    parent[rootY] = rootX;\n                } else if (rank[rootX] < rank[rootY]) {\n                    parent[rootX] = rootY;\n                } else {\n                    parent[rootY] = rootX;\n                    rank[rootX]++;\n                }\n                count--;\n                return true;\n            }\n            return false;\n        }\n        public int getCount() {\n            return count;\n        }\n    }\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        UnionFind aliceUF = new UnionFind(n);\n        UnionFind bobUF = new UnionFind(n);\n        int addedEdges = 0;\n        Arrays.sort(edges, (a, b) -> b[0] - a[0]);\n        for (int[] edge : edges) {\n            int type = edge[0];\n            int u = edge[1] - 1;\n            int v = edge[2] - 1;\n\n            if (type == 3) {\n                boolean aliceConnected = aliceUF.union(u, v);\n                boolean bobConnected = bobUF.union(u, v);\n                if (aliceConnected || bobConnected) {\n                    addedEdges++;\n                }\n            } else if (type == 1) {\n                if (aliceUF.union(u, v)) {\n                    addedEdges++;\n                }\n            } else if (type == 2) {\n                if (bobUF.union(u, v)) {\n                    addedEdges++;\n                }\n            }\n        }\n        if (aliceUF.getCount() > 1 || bobUF.getCount() > 1) {\n            return -1;\n        }\n        return edges.length - addedEdges;\n    }\n\t}\n```
['Union Find', 'Graph', 'Sorting', 'Java']