数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：判断图是否可被所有人遍历
假设我们有一个包含n个顶点（编号为0到n-1）的图。该图是无向图，每条边都有权重。图的权重可以是三种类型，每种权重代表一项特定任务。有两个人可以遍历该图，分别是Jack和Casey。如果一条边的权重为1，Jack可以遍历该图；如果权重为2，Casey可以遍历该图；如果权重为3，Jack和Casey都可以遍历该图。我们必须移除必要的边以使图对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，则
如果`union(v, w)`不为零，则
`edge1 := edge1 + 1`
`edge2 := edge2 + 1`
否则，
`res := res + 1`
`root0 := root[0...n]`
对于每条边(u, v)及其权重w在e中，执行：
如果u等于1，则
如果`union(v, w)`不为零，则
`edge1 := edge1 + 1`
否则，
`res := res + 1`
`root := root0`
对于每条边(u, v)及其权重w在e中，执行：
如果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
浏览量：133
