题目描述

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：

• 类型 1：只能由 Alice 遍历。
• 类型 2：只能由 Bob 遍历。
• 类型 3：Alice 和 Bob 都可以遍历。

给定一个数组 edges，其中 edges[i] = [type_i, u_i, v_i] 表示节点 u_i 和 v_i 之间存在类型为 type_i 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1。

样例

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。
再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2。

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4。
类似地，Bob 也不能达到节点 1。
因此，图无法完全遍历。

限制

• 1 <= n <= 10^5
• 1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
• edges[i].length == 3
• 1 <= edges[i][0] <= 3
• 1 <= edges[i][1] < edges[i][2] <= n
• 所有元组 (type_i, u_i, v_i) 互不相同。

算法

(贪心，并查集) $O(n + m)$

1. 将整个过程看做加边的操作。先遍历一次边集数组，优先加入类型为 3 的边。
2. 维护两个并查集，分别表示 Alice 和 Bob 的连通情况。
3. 加类型 3 的边时，如果发现 Alice 或 Bob 不连通（事实上二者应该一致），则两个并查集都进行合并当前边的两个节点；否则，这条边就是冗余的。
4. 加类型 1 或 2 的边时同理，单独判断 Alice 或 Bob 的连通性，操作对应的并查集。
5. 最后注意判断 Alice 和 Bob 是否都连通。

时间复杂度

• 遍历边集数组两次，并查集的操作时间复杂度为常数，故时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储并查集的数据结构。

C++ 代码

class UnionFind {
public:
    vector<int> f, sz;

    UnionFind(int n) {
        f.resize(n);
        sz.resize(n, 1);
        for (int i = 0; i < n; i++)
            f[i] = i;
    }

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;

        if (sz[fx] < sz[fy]) {
            f[fx] = fy;
            sz[fy] += sz[fx];
        } else {
            f[fy] = fx;
            sz[fx] += sz[fy];
        }
    }
};

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        UnionFind a(n), b(n);

        int ans = 0;
        for (const auto &e : edges) {
            int x = e[1] - 1, y = e[2] - 1;
            if (e[0] != 3) continue;

            if (e[0] == 3) {
                if (a.find(x) != a.find(y) || b.find(x) != b.find(y)) {
                    a.merge(x, y);
                    b.merge(x, y);
                } else {
                   ans++;
                }
            }
        }

        for (const auto &e : edges) {
            int x = e[1]-1, y = e[2]-1;
            if (e[0] == 1) {
                if (a.find(x) != a.find(y)) a.merge(x, y);
                else ans++;
            } else if (e[0] == 2) {
                if (b.find(x) != b.find(y)) b.merge(x, y);
                else ans++;
            }
        }

        if (a.sz[a.find(0)] != n || b.sz[b.find(0)] != n)
            return -1;

        return ans;
    }
};