---

1579. 保证图可完全遍历

• 标签：并查集、图
• 难度：困难

题目链接

• 1579. 保证图可完全遍历 - 力扣

题目大意

描述：给定一个 $n$ 个节点的无向图，以及边集 $edges$。每条边有类型 $type$：

• $type=1$：只能由 Alice 走（仅 Alice 可通行）。
• $type=2$：只能由 Bob 走。
• $type=3$：两人都可以走（公共边）。

要求：删除尽可能多的边，使得删除后 Alice 和 Bob 各自都能访问所有节点。返回最多可以删除的边数。如果无法让两人都完全遍历，返回 $-1$。

说明：

• $1 \le n \le 10^5$。
• $1 \le edges.length \le 2 \times 10^5$。

示例：

• 示例 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 。

• 示例 2：

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

解题思路

思路 1：并查集 + 贪心

1. 核心思想

首先使用公共边（$type=3$）连接节点，因为一条公共边可以同时满足两个人的连通需求，是最"划算"的。

然后分别用 Alice 的边（$type=1$）和 Bob 的边（$type=2$）补充连通性。

最终保留的边数 = 公共边中使用的数量 + Alice 使用的 $type=1$ 边数 + Bob 使用的 $type=2$ 边数。

删除的边数 = 总边数 - 保留的边数。

2. 具体步骤

第 1 步：初始化两个并查集 $uf\_a$ 和 $uf\_b$（分别用于 Alice 和 Bob）。

第 2 步：先处理 $type=3$ 的边：

• 如果在 $uf\_a$ 中 $u$ 和 $v$ 不连通，则使用该边（合并），同时也在 $uf\_b$ 中合并。
• 如果已经连通，该边可删除，计数加 $1$。

第 3 步：分别处理 $type=1$ 的边（Alice）和 $type=2$ 的边（Bob）：

• 对于各自的并查集，如果 $u$ 和 $v$ 不连通，则使用。
• 如果已连通，该边可删除，计数加 $1$。

第 4 步：检查 Alice 和 Bob 是否各自连通所有节点（连通分量数 $= 1$）。如果不是，返回 $-1$。

第 5 步：返回可删除的边数。

3. 为什么先处理公共边？

公共边能同时满足两个人的需求，优先使用可以最大化删除的边数。如果一条公共边对一个人来说已经多余（通过其他公共边连通），但对另一个人来说还有用，那它还是有保留价值的。但贪心先处理公共边能保证最优。

4. 举例说明

以 $n=4, edges=[[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]$ 为例：

先处理公共边：

• $[1,2]$：合并 A: {1,2}, B: {1,2}。
• $[2,3]$：合并 A: {1,2,3}, B: {1,2,3}。

Alice 边：

• $[1,3]$：已连通，删除。
• $[2,4]$：A: {1,2,3,4}，使用。
• $[1,2]$：已连通，删除。

Bob 边：

• $[3,4]$：B: {1,2,3,4}，使用。

总边数 $6$，使用 $4$ 条（2 公共 + 1 Alice + 1 Bob），删除 $2$ 条。

思路 1：代码

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        self.parent[ry] = rx
        return True

    def is_connected(self):
        root = self.find(0)
        return all(self.find(i) == root for i in range(len(self.parent)))

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        uf_a = UnionFind(n)
        uf_b = UnionFind(n)
        remove = 0

        # 先处理公共边
        for t, u, v in edges:
            if t == 3:
                u -= 1
                v -= 1
                if not uf_a.union(u, v):
                    remove += 1
                else:
                    uf_b.union(u, v)

        # 处理 Alice 和 Bob 各自的边
        for t, u, v in edges:
            u -= 1
            v -= 1
            if t == 1:
                if not uf_a.union(u, v):
                    remove += 1
            elif t == 2:
                if not uf_b.union(u, v):
                    remove += 1

        if not uf_a.is_connected() or not uf_b.is_connected():
            return -1

        return remove

思路 1：复杂度分析

• 时间复杂度：$O((n + m) \times \alpha(n))$，近似线性。
• 空间复杂度：$O(n)$。