Easy Peasy 💯 👍
Method: maxNumEdgesToRemove\nInitialization:\n\nTwo UnionFind instances are created: aliceUF and bobUF for Alice and Bob, respectively.\nAn addedEdges counter i
Method: maxNumEdgesToRemove\nInitialization:\n\nTwo UnionFind instances are created: aliceUF and bobUF for Alice and Bob, respectively.\nAn addedEdges counter is initialized to zero to keep track of the number of edges that have been added to the graph.\nProcessing Type 3 Edges:\n\nThe edges are processed in two passes. In the first pass, only type 3 edges (usable by both Alice and Bob) are considered.\nFor each type 3 edge, the union operation is performed on both aliceUF and bobUF.\nIf either union operation is successful, the edge is counted in addedEdges.\nProcessing Type 1 and Type 2 Edges:\n\nIn the second pass, type 1 and type 2 edges are processed separately.\nFor type 1 edges (usable by Alice only), the union operation is performed on aliceUF.\nFor type 2 edges (usable by Bob only), the union operation is performed on bobUF.\nIf the union operation is successful, the edge is counted in addedEdges.\nChecking Connectivity:\n\nAfter processing all edges, the connectivity of both Alice\'s and Bob\'s graphs is checked.\nIf either graph is not fully connected (i.e., the count of disjoint sets is more than 1), the method returns -1.\nCalculating Removable Edges:\n\nThe maximum number of edges that can be removed is calculated as the total number of edges minus the number of edges that have been added.\nExample Table for Clarification\nLet\'s consider an example with n = 4 and edges = {{3,1,2}, {3,2,3}, {1,1,3}, {1,2,4}, {1,1,2}, {2,3,4}}.\n![image](https://assets.leetcode.com/users/images/f2c8ce94-4d1f-423d-8187-3219c7750f53_1719706764.3366597.jpeg)\nFinal Check\naliceUF.getCount() > 1 or bobUF.getCount() > 1: Both are false since both graphs are fully connected.\nTotal edges = 6, addedEdges = 5.\nMaximum edges removable = 6 - 5 = 1.\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```\n```\nclass UnionFind:\n    def __init__(self, n: int):\n        self.parent = list(range(n))\n        self.rank = [0] * n\n        self.count = n\n\n    def find(self, x: int) -> int:\n        if self.parent[x] != x:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n\n    def union(self, x: int, y: int) -> bool:\n        rootX = self.find(x)\n        rootY = self.find(y)\n        \n        if rootX != rootY:\n            if self.rank[rootX] > self.rank[rootY]:\n                self.parent[rootY] = rootX\n            elif self.rank[rootX] < self.rank[rootY]:\n                self.parent[rootX] = rootY\n            else:\n                self.parent[rootY] = rootX\n                self.rank[rootX] += 1\n            self.count -= 1\n            return True\n        return False\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        aliceUF = UnionFind(n)\n        bobUF = UnionFind(n)\n        addedEdges = 0\n\n        for edge in edges:\n            if edge[0] == 3:\n                u, v = edge[1] - 1, edge[2] - 1\n                aliceConnected = aliceUF.union(u, v)\n                bobConnected = bobUF.union(u, v)\n                if aliceConnected or bobConnected:\n                    addedEdges += 1\n        for edge in edges:\n            if edge[0] == 1:\n                u, v = edge[1] - 1, edge[2] - 1\n                if aliceUF.union(u, v):\n                    addedEdges += 1\n            elif edge[0] == 2:\n                u, v = edge[1] - 1, edge[2] - 1\n                if bobUF.union(u, v):\n                    addedEdges += 1\n        if aliceUF.count > 1 or bobUF.count > 1:\n            return -1\n        return len(edges) - addedEdges\n```\n```\nclass UnionFind {\npublic:\n    vector<int> parent;\n    vector<int> rank;\n    int count;\n\n    UnionFind(int n) : parent(n), rank(n, 0), count(n) {\n        for (int i = 0; i < n; ++i) {\n            parent[i] = i;\n        }\n    }\n\n    int find(int x) {\n        if (parent[x] != x) {\n            parent[x] = find(parent[x]);\n        }\n        return parent[x];\n    }\n\n    bool unionSets(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\n    int getCount() {\n        return count;\n    }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        UnionFind aliceUF(n), bobUF(n);\n        int addedEdges = 0;\n\n        for (const auto& edge : edges) {\n            if (edge[0] == 3) {\n                int u = edge[1] - 1;\n                int v = edge[2] - 1;\n                bool aliceConnected = aliceUF.unionSets(u, v);\n                bool bobConnected = bobUF.unionSets(u, v);\n                if (aliceConnected || bobConnected) {\n                    addedEdges++;\n                }\n            }\n        }\n\n        for (const auto& edge : edges) {\n            if (edge[0] == 1) {\n                int u = edge[1] - 1;\n                int v = edge[2] - 1;\n                if (aliceUF.unionSets(u, v)) {\n                    addedEdges++;\n                }\n            } else if (edge[0] == 2) {\n                int u = edge[1] - 1;\n                int v = edge[2] - 1;\n                if (bobUF.unionSets(u, v)) {\n                    addedEdges++;\n                }\n            }\n        }\n\n        if (aliceUF.getCount() > 1 || bobUF.getCount() > 1) {\n            return -1;\n        }\n\n        return edges.size() - addedEdges;\n    }\n};\n```\n![image](https://assets.leetcode.com/users/images/8c277bad-ef3a-4ade-bc76-4e9416d6cb7c_1719707291.9463017.jpeg)\n\n
['Java']