确定图形是否可以被 Python 中的每个人遍历的程序
假设给定一个图，其中包含 n 个顶点，编号为 0 到 n - 1。该图是无向的，每条边都有一个权重。该图可以具有三种类型的权重，每种权重都表示一个特定的任务。有两个人可以遍历图，即 Jack 和 Casey。如果边的权重为 1，Jack 可以遍历图，如果边的权重为 2，Casey 可以遍历图，如果边的权重为 3，则两者都可以遍历图。我们必须删除任何必要的边以使图对两者都可遍历杰克和凯西。我们返回要删除的边数以使图可遍历，或者如果无法使其可遍历，则返回 -1。
所以，如果输入像
n = 5；那么输出将是-1
不能通过删除一条边使图对两者都可遍历。所以，答案是-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 中的每个人遍历的程序 的全部内容， 来源链接： utcz.com/z/363237.html
