Solution By Dare2Solve | Detailed Explanation | Union Find | Clean Code
Explanation []\nauthorslog.vercel.app/blog/O3ildCY4Uu\n\n\n# Code\n\ncpp []\nclass UnionFind {\npublic:\n    vector<int> parent;\n    int groups;\n\n    UnionFi
```Explanation []\nauthorslog.vercel.app/blog/O3ildCY4Uu\n```\n\n# Code\n\n```cpp []\nclass UnionFind {\npublic:\n    vector<int> parent;\n    int groups;\n\n    UnionFind(int n) : parent(n), groups(n - 1) {\n        for (int i = 0; i < n; ++i) {\n            parent[i] = i;\n        }\n    }\n\n    int find(int i) {\n        if (parent[i] != i) {\n            parent[i] = find(parent[i]);\n        }\n        return parent[i];\n    }\n\n    bool unionSets(int i, int j) {\n        int x = find(i);\n        int y = find(j);\n        if (x == y) {\n            return false;\n        } else {\n            parent[y] = x;\n            --groups;\n            return true;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        UnionFind alice(n), bob(n);\n        int count = 0;\n\n        for (const auto& edge : edges) {\n            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;\n            if (type == 3 && alice.unionSets(u, v) && bob.unionSets(u, v)) {\n                ++count;\n            }\n        }\n        for (const auto& edge : edges) {\n            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;\n            if ((type == 1 && alice.unionSets(u, v)) || (type == 2 && bob.unionSets(u, v))) {\n                ++count;\n            }\n        }\n\n        if (alice.groups == 0 && bob.groups == 0) {\n            return edges.size() - count;\n        } else {\n            return -1;\n        }\n    }\n};\n```\n\n```python []\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.groups = n - 1\n        \n    def find(self, i):\n        if self.parent[i] != i:\n            self.parent[i] = self.find(self.parent[i])\n        return self.parent[i]\n    \n    def union(self, i, j):\n        x = self.find(i)\n        y = self.find(j)\n        if x == y:\n            return False\n        else:\n            self.parent[y] = x\n            self.groups -= 1\n            return True\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        alice = UnionFind(n)\n        bob = UnionFind(n)\n        count = 0\n        \n        for edge in edges:\n            type, u, v = edge[0], edge[1] - 1, edge[2] - 1\n            if type == 3 and alice.union(u, v) and bob.union(u, v):\n                count += 1\n        \n        for edge in edges:\n            type, u, v = edge[0], edge[1] - 1, edge[2] - 1\n            if (type == 1 and alice.union(u, v)) or (type == 2 and bob.union(u, v)):\n                count += 1\n        \n        if alice.groups == 0 and bob.groups == 0:\n            return len(edges) - count\n        else:\n            return -1\n```\n\n```java []\nclass UnionFind {\n    int[] parent;\n    int groups;\n\n    UnionFind(int n) {\n        parent = new int[n];\n        for (int i = 0; i < n; ++i) {\n            parent[i] = i;\n        }\n        groups = n - 1;\n    }\n\n    int find(int i) {\n        if (parent[i] != i) {\n            parent[i] = find(parent[i]);\n        }\n        return parent[i];\n    }\n\n    boolean union(int i, int j) {\n        int x = find(i);\n        int y = find(j);\n        if (x == y) {\n            return false;\n        } else {\n            parent[y] = x;\n            groups--;\n            return true;\n        }\n    }\n}\n\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        UnionFind alice = new UnionFind(n);\n        UnionFind bob = new UnionFind(n);\n        int count = 0;\n\n        for (int[] edge : edges) {\n            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;\n            if (type == 3 && alice.union(u, v) && bob.union(u, v)) {\n                ++count;\n            }\n        }\n        for (int[] edge : edges) {\n            int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;\n            if ((type == 1 && alice.union(u, v)) || (type == 2 && bob.union(u, v))) {\n                ++count;\n            }\n        }\n\n        if (alice.groups == 0 && bob.groups == 0) {\n            return edges.length - count;\n        } else {\n            return -1;\n        }\n    }\n}\n```\n\n```javascript []\n/**\n * @param {number} n\n * @param {number[][]} edges\n * @returns {number}\n */\nvar maxNumEdgesToRemove = function (n, edges) {\n    const alice = new UnionFind(n), bob = new UnionFind(n);\n    let count = 0;\n\n    for (let [type, u, v] of edges) {\n        if (type === 3 && alice.union(u, v) && bob.union(u, v)) count++;\n    }\n    for (let [type, u, v] of edges) {\n        if (\n            (type === 1 && alice.union(u, v)) ||\n            (type === 2 && bob.union(u, v))\n        )\n            count++;\n    }\n\n    if (!bob.groups && !alice.groups) return edges.length - count;\n    else return -1;\n};\n\n/**\n * @class UnionFind\n * @param {number} n\n */\nclass UnionFind {\n    constructor(n) {\n        this.parent = new Array(n).fill().map((_, i) => i);\n        this.groups = n - 1;\n    }\n\n    /**\n     * @param {number} i\n     * @returns {number}\n     */\n    find(i) {\n        if (this.parent[i] !== i) this.parent[i] = this.find(this.parent[i]);\n        return this.parent[i];\n    }\n\n    /**\n     * @param {number} i\n     * @param {number} j\n     * @returns {boolean}\n     */\n    union(i, j) {\n        const x = this.find(i),\n            y = this.find(j);\n        if (x === y) return false;\n        else {\n            this.parent[y] = x;\n            this.groups--;\n            return true;\n        }\n    }\n}\n```
['Union Find', 'Graph', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']