C++ Union Find with explanation
See my latest update in repo LeetCode\n\n## Solution 1. Union Find\n\nCreate two UnionFinds a and b for Alice and Bob respectively.\n\nWe should take type 3 edg
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Union Find\n\nCreate two UnionFinds `a` and `b` for Alice and Bob respectively.\n\nWe should take type 3 edges first, then type 1 and 2.\n\nIf two nodes are already connected, we increment the answer `ans`. Otherwise we connect them.\n\nIn the end, if `a.getSize() == 1 && b.size() == 1` meaning that the graph is all connected for both Alice and Bob, we return `ans`; otherwise return `-1`.\n\n```cpp\n// OJ: https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/\n// Author: github.com/lzl124631x\n// Time: O(N + E)\n// Space: O(N)\nclass UnionFind{\n    vector<int> id;\n    int size;\npublic:\n    UnionFind(int N ): id(N), size(N) {\n        iota(begin(id), end(id), 0);\n    }\n    int find(int a) {\n        return id[a] == a ? a : (id[a] = find(id[a]));\n    }\n    int connected(int a, int b) {\n        return find(a) == find(b);\n    }\n    void connect(int a, int b) {\n        int p = find(a), q = find(b);\n        if (p == q) return;\n        id[p] = q;\n        --size;\n    }\n    int getSize() { return size; }\n};\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& E) {\n        UnionFind a(n), b(n);\n        int ans = 0;\n        for (auto &e : E) {\n            if (e[0] != 3) continue;\n            int u = e[1] - 1, v = e[2] - 1;\n            if (a.connected(u, v)) {\n                ++ans;\n                continue;\n            }\n            a.connect(u, v);\n            b.connect(u, v);\n        }\n        for (auto &e : E) {\n            int u = e[1] - 1, v = e[2] - 1;\n            if (e[0] == 1) {\n                if (a.connected(u, v)) ++ans;\n                else a.connect(u, v);\n            } else if (e[0] == 2) {\n                if (b.connected(u, v)) ++ans;\n                else b.connect(u, v);\n            }\n        }\n        return a.getSize() != 1 || b.getSize() != 1 ? -1 : ans;\n    }\n};\n```\n\n---\n\nThe following code can beat 100% (~1000ms run time) but the idea is exactly the same.\n\n```cpp\n// OJ: https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/\n// Author: github.com/lzl124631x\n// Time: O(N + E)\n// Space: O(N)\n// The following block might trivially improve the exec time.\nstatic const auto __optimize__ = []() {\n    std::ios::sync_with_stdio(false);\n    std::cin.tie(NULL);\n    return 0;\n}();\nclass UnionFind{\n    vector<int> id;\n    int size;\npublic:\n    UnionFind(int N ): id(N), size(N) {\n        iota(begin(id), end(id), 0);\n    }\n    int find(int a) {\n        return id[a] == a ? a : (id[a] = find(id[a]));\n    }\n    int connected(int a, int b) {\n        return find(a) == find(b);\n    }\n    void connect(int a, int b) {\n        int p = find(a), q = find(b);\n        if (p == q) return;\n        id[p] = q;\n        --size;\n    }\n    int getSize() { return size; }\n};\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& E) {\n        UnionFind a(n), b(n);\n        int ans = 0;\n        for (auto &e : E) {\n            if (e[0] != 3) continue;\n            int u = e[1] - 1, v = e[2] - 1;\n            if (a.connected(u, v)) {\n                ++ans;\n                continue;\n            }\n            a.connect(u, v);\n            b.connect(u, v);\n        }\n        for (auto &e : E) {\n            if (e[0] != 1) continue;\n            int u = e[1] - 1, v = e[2] - 1;\n            if (a.connected(u, v)) ++ans;\n            else a.connect(u, v);\n        }\n        if (a.getSize() != 1) return -1;\n        for (auto &e : E) {\n            if (e[0] != 2) continue;\n            int u = e[1] - 1, v = e[2] - 1;\n            if (b.connected(u, v)) ++ans;\n            else b.connect(u, v);\n        }\n        return b.getSize() != 1 ? -1 : ans;\n    }\n};\n```
[]