LeetCode 题解工作台
保证图可完全遍历
Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边： 类型 1：只能由 Alice 遍历。 类型 2：只能由 Bob 遍历。 类型 3：Alice 和 Bob 都可以遍历。 给你一个数组 edges ，其中 edges[i] = [type i , u i , v i ]…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 并查集
答案摘要
题目要求我们删除最多数目的边，使得 Alice 和 Bob 都可以遍历整个图。也即是说，我们需要保留尽可能少的边，并且要求这些边能够使得 Alice 和 Bob 都可以遍历整个图。 我们可以用两个并查集 和 分别维护 Alice 和 Bob 的遍历情况。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
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^51 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)edges[i].length == 31 <= edges[i][0] <= 31 <= edges[i][1] < edges[i][2] <= n- 所有元组
(typei, ui, vi)互不相同
解题思路
方法一：贪心 + 并查集
题目要求我们删除最多数目的边，使得 Alice 和 Bob 都可以遍历整个图。也即是说，我们需要保留尽可能少的边，并且要求这些边能够使得 Alice 和 Bob 都可以遍历整个图。
我们可以用两个并查集 和 分别维护 Alice 和 Bob 的遍历情况。
接下来，我们优先遍历公共边，即 的边。对于每一条公共边的两个端点 和 ，如果这两个点已经在同一个连通分量中，那么我们就可以删去这条边，因此答案加一；否则我们就将这两个点合并，即执行 和 。
然后，我们再遍历 Alice 独有的边，即 的边。对于每一条 Alice 独有的边的两个端点 和 ，如果这两个点已经在同一个连通分量中，那么我们就可以删去这条边，答案加一；否则我们就将这两个点合并，即执行 。同理，对于 Bob 独有的边，我们也可以执行相同的操作。
最后，如果 Alice 和 Bob 都可以遍历整个图，那么答案就是我们删除的边数；否则答案就是 。
时间复杂度 ，空间复杂度 。其中 是边数，而 是阿克曼函数的反函数。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
self.cnt = n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a - 1), self.find(b - 1)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
self.cnt -= 1
return True
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
ufa = UnionFind(n)
ufb = UnionFind(n)
ans = 0
for t, u, v in edges:
if t == 3:
if ufa.union(u, v):
ufb.union(u, v)
else:
ans += 1
for t, u, v in edges:
if t == 1:
ans += not ufa.union(u, v)
if t == 2:
ans += not ufb.union(u, v)
return ans if ufa.cnt == 1 and ufb.cnt == 1 else -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Familiarity with Union Find techniques and optimizations.
- question_mark
Understanding of graph traversal and edge prioritization.
- question_mark
Ability to handle large inputs efficiently using path compression and union by rank.
常见陷阱
外企场景- error
Forgetting to handle all types of edges properly, leading to unnecessary removals.
- error
Not correctly applying Union Find operations, leading to incorrect traversal determination.
- error
Overlooking edge prioritization, which can result in suboptimal edge removal.
进阶变体
外企场景- arrow_right_alt
Implement the solution with DFS or BFS to explore graph connectivity before removing edges.
- arrow_right_alt
Handle more edge types with different traversal requirements.
- arrow_right_alt
Optimize the solution for higher input limits by improving the Union Find structure.