1579. 保证图可完全遍历
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/
题目
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：
- 类型 1：只能由 Alice 遍历。
- 类型 2：只能由 Bob 遍历。
- 类型 3：Alice 和 Bob 都可以遍历。
给你一个数组
edges
，其中
edges[i] = [typei, ui, vi]
表示节点
ui
和
vi
之间存在类型为
typei
的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
示例 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 无法完全遍历这个图。
示例 3：
输入：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
- 所有元组
(typei, ui, vi)
以上图源来自：力扣（LeetCode）
解题思路
思路：并查集
先审题，题目给定一个无向图，由 A l i c e Alice Alice 和 B o b Bob Bob 共有，其中无向图含有 n n n 个节点，以及存在限制的 3 种类型的边：
- 类型 1：仅能由 A l i c e Alice Alice 遍历；
- 类型 2：仅能由 B o b Bob Bob 遍历；
- 类型 3：属于共有边， A l i c e Alice Alice 和 B o b Bob Bob 均能遍历。
这些类型的边由数组 e d g e s edges edges 给出，其中 e d g e s [ i ] = [ t y p e i , u i , v i ] edges[i] = [type_i,\, u_i,\, v_i] edges[i]=[typei,ui,vi]，表示存在连接 u i u_i ui 和 v i v_i vi 的边，边的类型为 t y p e i type_i typei。
现在题目要求保证图能被 A l i c e Alice Alice 和 B o b Bob Bob 都完全遍历的前提下，找到能够删除最大数目的边的数量。其中，这里所说图能够被完全遍历是指从任何节点开始， A l i c e Alice Alice 和 B o b Bob Bob 均能到达所有其他节点。
即是：
- 当图仅存在 【类型 1】和【类型 3】的边时，图能够连通，那么就表示图能够被 A l i c e Alice Alice 完全遍历；
- 当图仅存在 【类型 2】和【类型 3】的边时，图能够连通，那么就表示图能够被 B o b Bob Bob 完全遍历。
以上两种情形，图能够连通，那么表明图最终只会剩下 1 个连通分量。那么题目要求能够删除最大数目边的数量，即是指两种情形下图能连通时，所使用的边要尽可能少。
因为图存在 3 种类型的边，这里要先讨论下优先级的问题。先说结论：【类型 3】的边要优于【类型 1】和【类型 2】的边，优先考虑使用【类型 3】 的边。
这里说下缘由，如果存在两个节点，当考虑使用【类型 3】的边进行连接时，那么 A l i c e Alice Alice 和 B o b Bob Bob 均能遍历；但若不考虑使用【类型 3】的边，那么就必须添加仅自身能访问的 2 种不同类型的边，只有这样才能保证自身能够遍历到达两个节点。而这显然不符合上面所述使用尽可能少的边的要求，所以优先考虑使用【类型 3】的边。
题目仅考虑连通性的问题，我们用并查集的方法来解决。
首先先考虑边为【类型 3】的情况，进行遍历，对于两个节点的连接情况进行判断：
- 如果两个节点处于同个连通分量中，那么这条边属于可删除边，进行统计；
- 如果两个节点不处于同个连通分量，那么选用这条边，将两个节点进行合并。
处理完之后，再分别考虑【类型 1】和【类型 2】的边，处理方案与上面相同。遍历，如果边连接的两个节点属于同个连通分量，属于可删除边，进行统计；否则选用这条边，合并两个节点。
下面用图示来看下大致实现的过程：
最后，说下代码需注意的地方，题目提示中说明 1 ≤ e d g e s [ i ] [ 1 ] < e d g e s [ i ] [ 2 ] ≤ n 1 \leq edges[i][1] < edges[i][2] \leq n 1≤edges[i][1]<edges[i][2]≤n，也就是节点并非从 0 开始，那么并查集初始化数组长度应为 n + 1 n+1 n+1，初始连通分量数目也为 n + 1 n+1 n+1 个。
根据上面的做法，若图能够连通，由于图没有节点 0，节点 0 最终也是单独一个连通分量，而其他所有节点则合并成的一个连通分量。最后判断连通分量数目应该是判断是否大于 2，当大于 2，则表示图无法连通，无法被完全遍历。
具体代码实现如下。
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.count = n
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return False
self.parent[x_root] = y_root
self.count -= 1
return True
def get_count(self):
return self.count
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
uf_alice = UnionFind(n+1)
uf_bob = UnionFind(n+1)
res = 0
for tp, u, v in edges:
if tp == 3:
if not uf_alice.union(u, v):
res += 1
else:
uf_bob.union(u, v)
for tp, u, v in edges:
if tp == 1:
if not uf_alice.union(u, v):
res += 1
if tp == 2:
if not uf_bob.union(u, v):
res += 1
if uf_alice.get_count() - 1 > 1 or uf_bob.get_count() - 1 > 1:
return -1
return res
欢迎关注
公众号 【书所集录】
如有错误，烦请指出，欢迎指点交流。若觉得写得还不错，麻烦点个赞👍，谢谢。