leetcode如何保证图可完全遍历
这篇文章主要介绍“leetcode如何保证图可完全遍历”，在日常操作中，相信很多人在leetcode如何保证图可完全遍历问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”leetcode如何保证图可完全遍历”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
网站建设哪家好，找创新互联建站！专注于网页设计、网站建设、微信开发、微信小程序定制开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了黑龙江免费建站欢迎大家使用！
一、题目内容
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) 互不相同
二、解题思路
维护三种线段的连通关系，线段3一般要保留，毕竟是公用的。
具体思路看代码注释。
三、代码
class Solution: def maxNumEdgesToRemove(self, n: int, edges: list) -> int: uf1 = UnionFind(n) uf2 = UnionFind(n) uf3 = UnionFind(n) count1 = 0 # 线段1的个数 count2 = 0 # 线段2的个数 count3 = 0 # 线段3的个数 redundant_count3 = 0 # 线段3冗余的个数 for i in range(len(edges)): edge_type = edges[i][0] # 线段种类 st = edges[i][1] - 1 ed = edges[i][2] - 1 # 记录每种线段的个数 if edge_type == 1: count1 += 1 elif edge_type == 2: count2 += 1 elif edge_type == 3: count3 += 1 else: raise ValueError # 每种线段进行连通 if edge_type == 1 or edge_type == 3: uf1.Union(st, ed) if edge_type == 2 or edge_type == 3: uf2.Union(st, ed) if edge_type == 3: if not uf3.isConnected(st, ed): uf3.Union(st, ed) else: # 已经连通说明冗余 redundant_count3 += 1 # 线段3直接连通了所有点 if uf3.getCount() == 1: return count1 + count2 + redundant_count3 # 删除的边可以是线段1+线段2+线段3冗余的个数 # 线段1和线段2同时连通， 那么都可以走的路不需要删除，也就是线段3不需要删除，但是要删除线段3的冗余 if uf1.getCount() == 1 and uf2.getCount() == 1: return count1 - (uf3.getCount() - 1) + \ count2 - (uf3.getCount() - 1) + redundant_count3 return -1 class UnionFind: def __init__(self, n): self.count = n self.root = [0 for _ in range(n)] self.size = [0 for _ in range(n)] for i in range(n): self.root[i] = i self.size[i] = i def find(self, x): if x != self.root[x]: self.root[x] = self.find(self.root[x]) return self.root[x] else: return x def isConnected(self, x, y): return self.find(x) == self.find(y) def getCount(self): return self.count def Union(self, x, y): # 查找x和y的根/父节点 rx = self.find(x) ry = self.find(y) # 根/父节点相同， 说明已经连通了 if rx == ry: return # 直接返回 if self.size[rx] < self.size[ry]: self.root[rx] = ry self.size[ry] += self.size[rx] else: self.root[ry] = rx self.size[rx] += self.size[ry] self.count -= 1 if __name__ == '__main__': s = Solution() n = 4 edges = [[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]] ans = s.maxNumEdgesToRemove(n, edges) print(ans)
到此，关于“leetcode如何保证图可完全遍历”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！
分享名称：leetcode如何保证图可完全遍历
网址分享：http://scyanting.com/article/jodceh.html
