使用Python编写程序以找出图形是否可由所有人穿过

假设我们有一个包含编号为0至n – 1的n个顶点的图形。图形是无向的，每个边缘都有一个重量。图形可以有三种类型的重量，每种重量都表示特定的任务。有两个人可以穿越图形，分别是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）和其权重w，在e中进行操作，执行
- 如果u与3相同，则
  - 如果联合（v，w）为非零，则
  - edge1：=edge1 + 1
  - edge2：=edge2 + 1
  - 否则，
  - res：=res + 1
root0：=root [从索引0到末尾]
对于每个边（u，v）和其权重w，在e中进行操作，执行
- 如果u与1相同，则
  - 如果联合（v，w）为非零，则
  - edge1：=edge1 + 1
  - 否则，
  - res：=res+ 1
- root：=root0
- 对于每个边（u，v）和其权重w，在e中进行操作，执行
  - 如果u与2相同，则
  - 如果联合（v，w）为非零，则
    - edge2：=edge2 + 1
  - 否则，
    - res：=res + 1
- 如果edge1与edge2，n-1相同，则返回res
- 否则，返回-1

示例

让我们看下面的实现以获得更好的理解

“`python 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)]))