这篇文章主要介绍“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://cdkjz.cn/article/jodceh.html
