保证图可完全遍历
难度:
标签:
题目描述
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)
互不相同
代码结果
运行时间: 238 ms, 内存: 52.7 MB
解释
方法:
这道题目利用并查集来解决。首先为Alice和Bob各创建一个并查集来跟踪他们各自能够访问的节点。处理类型3的边(Alice和Bob都可以使用的边)时,首先尝试合并两个节点,如果已经在同一个集合中则认为这条边是多余的,可以删除。然后独立处理类型1和类型2的边,对于Alice和Bob的并查集分别进行操作。如果操作后两个并查集都只剩下一个集合,说明图可以被完全遍历;否则返回-1表示无法遍历。
时间复杂度:
O(E)
空间复杂度:
O(N)
代码细节讲解
🦆
并查集的初始化中,为什么每个节点的父节点初始状态是None而不是节点自身?
▷🦆
在处理类型3的边时,如果一条边已经在Alice或Bob的并查集中,为什么还需要检查它在另一个并查集中是否存在?
▷🦆
为什么在处理类型1和类型2的边时,即使这些边被算作多余也要继续尝试合并操作?
▷🦆
在最终返回结果之前,如何通过并查集确定Alice和Bob是否能够完全遍历整个图?
▷