💯✅🔥Easy Java ,Python3 ,C++ Solution|| 32 ms ||≧◠‿◠≦✌
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem of "Maximum Number of Edges to Remove to Ensure Graph Connectivity" can be 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem of "Maximum Number of Edges to Remove to Ensure Graph Connectivity" can be solved using a Union-Find data structure. The idea is to group the nodes into connected components and then remove the edges that are not necessary for maintaining the connectivity of the graph.\n\n---\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach taken in the provided code is as follows:\n1. Sort the edges in descending order of their type (type 3, then type 2, then type 1).\n1. Create two Union-Find data structures, one for Alice and one for Bob.\n1. Iterate through the sorted edges and process them as follows:\n    - For type 3 edges, try to unite the nodes in both Alice\'s and Bob\'s Union-Find structures. If either of the unions is successful, increment the edgeAdd counter.\n    -  For type 2 edges, try to unite the nodes in Bob\'s Union-Find structure. If the union is successful, increment the edgeAdd counter.\n    - For type 1 edges, try to unite the nodes in Alice\'s Union-Find structure. If the union is successful, increment the edgeAdd counter.\n1. After processing all the edges, check if both Alice and Bob have a single connected component (i.e., their Union-Find structures are united). If so, return the number of edges that were not added (edges.length - edgeAdd). Otherwise, return -1 to indicate that it\'s not possible to ensure connectivity for both Alice and Bob.\n---\n# Complexity\n- Time complexity:O(n log n).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n---\n- Space complexity:O(n).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n---\n# Code\n```java []\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        Arrays.sort(edges, (a, b) -> b[0] - a[0]);\n        \n        int edgeAdd = 0;\n        \n        UnionFind alice = new UnionFind(n);\n        UnionFind bob = new UnionFind(n);\n        \n        for (int[] edge : edges) {\n            int type = edge[0];\n            int a = edge[1];\n            int b = edge[2];\n            \n            switch (type) {\n                case 3:\n                    if (alice.unite(a, b) | bob.unite(a, b)) {\n                        edgeAdd++;\n                    }\n                    break;\n                case 2:\n                    if (bob.unite(a, b)) {\n                        edgeAdd++;\n                    }\n                    break;\n                case 1:\n                    if (alice.unite(a, b)) {\n                        edgeAdd++;\n                    } \n                    break;\n            }\n        }\n        \n        return (alice.united() && bob.united()) ? edges.length - edgeAdd : -1;\n    }\n    \n    private class UnionFind {\n        int[] component;\n        int distinctComponents;\n        \n        public UnionFind(int n) {\n            component = new int[n+1];\n            for (int i = 0; i <= n; i++) {\n                component[i] = i;\n            }\n            distinctComponents = n;\n        }\n        \n        private boolean unite(int a, int b) {\n            if (findComponent(a) != findComponent(b)) {\n                component[findComponent(a)] = b;\n                distinctComponents--;\n                return true;\n            }\n            \n            return false;\n        }\n        \n        private int findComponent(int a) {\n            if (component[a] != a) {\n                component[a] = findComponent(component[a]);\n            }\n            return component[a];\n        }\n        \n        private boolean united() {\n            return distinctComponents == 1;\n        }\n        \n    }\n}\n```\n```python3 []\nclass UnionFind:\n    """A minimalist standalone union-find implementation."""\n    def __init__(self, n):\n        self.count = n               # number of disjoint sets \n        self.parent = list(range(n)) # parent of given nodes\n        self.rank = [1]*n            # rank (aka size) of sub-tree \n        \n    def find(self, p):\n        """Find with path compression."""\n        if p != self.parent[p]: \n            self.parent[p] = self.find(self.parent[p]) # path compression \n        return self.parent[p]\n    \n    def union(self, p, q):\n        """Union with ranking."""\n        prt, qrt = self.find(p), self.find(q)\n        if prt == qrt: return False\n        self.count -= 1 # one more connection => one less disjoint \n        if self.rank[prt] > self.rank[qrt]: prt, qrt = qrt, prt # add small sub-tree to large sub-tree for balancing\n        self.parent[prt] = qrt\n        self.rank[qrt] += self.rank[prt] # ranking \n        return True\n    \n        \nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        ufa = UnionFind(n) # for Alice\n        ufb = UnionFind(n) # for Bob\n        \n        ans = 0\n        edges.sort(reverse=True) \n        for t, u, v in edges: \n            u, v = u-1, v-1\n            if t == 3: ans += not (ufa.union(u, v) and ufb.union(u, v)) # Alice & Bob\n            elif t == 2: ans += not ufb.union(u, v)                     # Bob only\n            else: ans += not ufa.union(u, v)                            # Alice only\n        return ans if ufa.count == 1 and ufb.count == 1 else -1 # check if uf is connected \n```\n```C++ []\nclass UnionFind {\n    vector<int> component;\n    int distinctComponents;\npublic:\n   \n    UnionFind(int n) {\n\t    distinctComponents = n;\n        for (int i=0; i<=n; i++) {\n            component.push_back(i);\n        }\n    }\n    \n    bool unite(int a, int b) {       \n        if (findComponent(a) == findComponent(b)) {\n            return false;\n        }\n        component[findComponent(a)] = b;\n        distinctComponents--;\n        return true;\n    }\n    \n    int findComponent(int a) {\n        if (component[a] != a) {\n            component[a] = findComponent(component[a]);\n        }\n        return component[a];\n    }\n    \n    bool united() {\n        return distinctComponents == 1;\n    }\n};\n\nclass Solution {\n    \npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        // Sort edges by their type such that all type 3 edges will be at the beginning.\n        sort(edges.begin(), edges.end(), [] (vector<int> &a, vector<int> &b) { return a[0] > b[0]; });\n        \n        int edgesAdded = 0; // Stores the number of edges added to the initial empty graph.\n        \n        UnionFind bob(n), alice(n); // Track whether bob and alice can traverse the entire graph,\n                                    // are there still more than one distinct components, etc.\n        \n        for (auto &edge: edges) { // For each edge -\n            int type = edge[0], one = edge[1], two = edge[2];\n            switch(type) {\n                case 3:\n                    edgesAdded += (bob.unite(one, two) | alice.unite(one, two));\n                    break;\n                case 2:\n                    edgesAdded += bob.unite(one, two);\n                    break;\n                case 1:\n                    edgesAdded += alice.unite(one, two);\n                    break;\n            }\n        }\n        \n        return (bob.united() && alice.united()) ? (edges.size()-edgesAdded) : -1; // Yay, solved.\n    }\n};\n```\n---\n![upvote.png](https://assets.leetcode.com/users/images/e6f4f26f-a7f5-465b-8ec1-aa665db072f9_1719537871.6475258.png)\n\n\n\n
['Union Find', 'Graph', 'C++', 'Java', 'Python3']