Cho đồ thị vô hướng edges = [u, v, w] và cạnh (a,b). Kiểm tra cạnh (a,b) có thuộc MST nào đó không. Đồ thị liên thông, cạnh (a,b) tồn tại.
Ví dụ: edges=[[0,2,100],[1,2,200],[1,3,100],[2,3,300]], a=0, b=2 → True.
Giải pháp
Dựa trên tính chất MST: cạnh (a,b) thuộc MST iff không tồn tại đường đi từ a đến b chỉ dùng cạnh có trọng số < w(a,b).
- Tìm weight của cạnh (a,b)
- Lọc edges chỉ giữ cạnh weight < weight
- Kiểm tra a, b có liên thông không trong đồ thị lọc (DFS)
- Nếu KHÔNG liên thông → cạnh (a,b) thuộc MST
Ví dụ minh họa
class Solution:
def findPath(self, edges, a, b):
if a == b:
return True
if not edges:
return False
for x in edges:
if x[2] == -1:
continue
new_a = -1
if x[0] == a:
new_a = x[1]
elif x[1] == a:
new_a = x[0]
if new_a != -1:
edges.remove(x)
if self.findPath(edges, new_a, b):
return True
edges.append(x)
return False
def solve(self, edges, a, b):
weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[2]
edges = [x for x in edges if x[2] < weight]
return not self.findPath(edges, a, b)
ob = Solution()
print(ob.solve([
[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]
], 0, 2))
Đầu vào
[[0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300]], 0, 2
Đầu ra
True