leetcode
leetcode 1401 ~ 1450
保证图可完全遍历

保证图可完全遍历

难度:

标签:

题目描述

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

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

给你一个数组 edges ,其中 edges[i] = [typei, ui, vi] 表示节点 uivi 之间存在类型为 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而不是节点自身?
在并查集的实现中,将每个节点的父节点初始化为None而不是其自身是为了区分根节点和未初始化的节点。这种做法允许在并查集操作中(如find和merge)更容易地管理和识别节点是否已经被访问过或加入到其他集合中。一旦节点进行了find操作或被合并到另一个节点,它的父节点将会被设置为指向它的根节点或另一个节点,这样就可以用None来表示一个节点是一个独立的根节点,即它自己就是一个集合的全部。
🦆
在处理类型3的边时,如果一条边已经在Alice或Bob的并查集中,为什么还需要检查它在另一个并查集中是否存在?
类型3的边是Alice和Bob都可以使用的边。当处理这类边时,即使这条边已经在Alice的并查集中存在,也需要确认它在Bob的并查集中也被合并,这样才能确保这条边对两个人的图遍历都产生作用。如果只在一个并查集中合并,而在另一个并查集中忽略,将可能导致某个人无法通过这条边连接到某些节点,从而无法完全遍历整个图。
🦆
为什么在处理类型1和类型2的边时,即使这些边被算作多余也要继续尝试合并操作?
即使在并查集中认为某些类型1或类型2的边是多余的(因为它们连接的两个节点已经在同一个集合中),仍然需要尝试进行合并操作,因为这可以确保算法的正确性和完整性。在实际操作中,这种多余的边的检测(通过检查两节点是否已连接)是在尝试合并之前进行的,这有助于在整个算法执行过程中维护并查集的当前状态,确保所有的边都被考虑过,即使它们不会改变并查集的结构。
🦆
在最终返回结果之前,如何通过并查集确定Alice和Bob是否能够完全遍历整个图?
可以通过检查每个并查集(Alice和Bob的)中的集合数量来确定是否可以完全遍历图。如果Alice的并查集只剩下一个集合,并且Bob的并查集也只剩下一个集合,这意味着所有节点都在各自的并查集中互相连接,因此可以完全遍历整个图。如果任一并查集中的集合数量大于1,则表示存在至少一个节点无法通过给定的边与其他节点连接,因此无法完全遍历图。这种方法确保了只有在两个并查集都完整连接的情况下,才认为图可以被完全遍历。

相关问题