用 Python 编写程序，判断该图是否可供所有人遍历
假设，我们得到一个包含 n 个顶点的图，编号从 0 到 n - 1。该图是无向的，每条边都有一个权重。该图可以有三种类型的权重，每种权重表示一项特定任务。有两个人可以遍历该图，分别是 Jack 和 Casey。如果边的权重为 1，Jack 可以遍历该图；如果边的权重为 2，Casey 可以遍历该图；如果边的权重为 3，两人都可以遍历该图。我们必须删除所有必要的边，以使该图可供 Jack 和 Casey 遍历。我们返回要移除的边数以使图可遍历，如果无法使图可遍历，则返回 -1。
因此，如果输入如下
并且 n =5；则输出将为 -1
通过移除一条边，无法使图对两者都可遍历。因此，答案是 -1。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 find() 。这将采用 val
如果 val 与 root[val] 不同，则
root[val] := find(root[val])
返回 root[val]
定义一个函数 union() 。这将采用 val1、val2
val1:= find(val1)
val2 := find(val2)
如果 val1 与 val2 相同，则
返回 0
root[val1] := val2
返回 1
res := 0
edge1 := 0
edge2 := 0
root := 一个范围从 0 到 n + 1 的新列表
对于每条边 (u, v) 及其在 e 中的权重 w，执行
如果 u 与 3 相同，则
如果 union(v, w)非零，则
edge1 := edge1 + 1
edge2 := edge2 + 1
否则，
res := res + 1
root0 := root[从索引 0 到末尾]
对于每条边 (u, v) 及其在 e 中的权重 w，执行
如果 u 与 1 相同，则
如果 union(v, w) 非零，则
edge1 := edge1 + 1
否则，
res := res + 1
root := root0
对于每条边 (u, v)，以及它在 e 中的权重 w，执行
如果 u 与 2 相同，则
如果 union(v, w) 非零，则
edge2 := edge2 + 1
否则，
res := res + 1
如果 edge1 与 edge2 相同且 n - 1，则返回 res
否则，返回 -1
示例
让我们看看下面的实现以便更好地理解
def solve(n, e):
def find(val):
if val != root[val]:
root[val] = find(root[val])
return root[val]
def union(val1, val2):
val1, val2 = find(val1), find(val2)
if val1 == val2: return 0
root[val1] = val2
return 1
res = edge1 = edge2 = 0
root = list(range(n + 1))
for u, v, w in e:
if u == 3:
if union(v, w):
edge1 += 1
edge2 += 1
else:
res += 1
root0 = root[:]
for u, v, w in e:
if u == 1:
if union(v, w):
edge1 += 1
else:
res += 1
root = root0
for u, v, w in e:
if u == 2:
if union(v, w):
edge2 += 1
else:
res += 1
return res if edge1 == edge2 == n - 1 else -1
print(solve(5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]))
输入
Input: 5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]
输出
-1
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
