原题地址（困难）

方法1—并查集

思路

见官方题解：

代码

size数组作用是保证两个连通子图相连时，每次都是把小的图连到大的图上，而不是把大的图连到小的图上，所以说其实不加size也没啥问题。

// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;
public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);  //给parent赋值为0
    }
    int findset(int x) {  // 寻找根
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
};
class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        UnionFind ufa(n), ufb(n);
        int ans = 0;
        // 节点编号改为从 0 开始
        for (auto& edge: edges) {
            --edge[1];
            --edge[2];
        }
        // 公共边
        for (const auto& edge: edges) {
            if (edge[0] == 3) {
                if (!ufa.unite(edge[1], edge[2]))    ++ans;
                else    ufb.unite(edge[1], edge[2]);
            }
        }
        // 独占边
        for (const auto& edge: edges) {
            if (edge[0] == 1) {
                // Alice 独占边
                if (!ufa.unite(edge[1], edge[2])) {
                    ++ans;
                }
            }
            else if (edge[0] == 2) {
                // Bob 独占边
                if (!ufb.unite(edge[1], edge[2])) {
                    ++ans;
                }
            }
        }
        if (ufa.setCount != 1 || ufb.setCount != 1) {
            return -1;
        }
        return ans;
    }
};