C++ Union-Find Both/One
Intuition\nWe would use union-find to solve this problem for one person. For two (or more) people, we first populate our "shared" disjoined set, using type 3 ed
#### Intuition\nWe would use union-find to solve this problem for one person. For two (or more) people, we first populate our "shared" disjoined set, using type 3 edges.\n\nThen, we process Alice and Bob independently, using the "shared" disjoined set as a starting point.\n\nEvery time we find a non-redundant edge, we increment `used`. We also check that the graph is fully connected for each person.\n\nIn the end, we can remove `total - used` edges.\n\n**C++**\n```cpp\nint find(vector<int> &ds, int i) {\n    return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);\n}\nint maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n    vector<int> ds_both(n + 1, -1);\n    int used = 0;\n    for (int type = 3; type > 0; --type) {\n        auto ds_one = ds_both;\n        auto &ds = type == 3 ? ds_both : ds_one;\n        for (auto &e : edges)\n            if (e[0] == type) {\n                int i = find(ds, e[1]), j = find(ds, e[2]);\n                if (i != j) {\n                    ++used;\n                    if (ds[j] < ds[i])\n                        swap(i, j);\n                    ds[i] += ds[j];\n                    ds[j] = i;\n                }\n            }\n        if (type != 3 && ds[find(ds, 1)] != -n)\n            return -1;\n    }\n    return edges.size() - used;\n}\n```\n**Complexity Analysis**\n- Time: O(m), where m is the number of edges. We go through all edges 3 times. The complexity of the `find` operation is O(\uD835\uDEFC(n)) as we use both rank and path compression. \uD835\uDEFC(n) can be considered a constant for all practical purposes.\n- Memory: O(n) for a disjoined set.
[]