确定图形是否可以被 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