คำอธิบายโจทย์
ให้กราฟ edges = [u, v, w] และ edge (a,b) ตรวจสอบว่า (a,b) อยู่ใน MST ใดๆ ได้หรือไม่ (กราฟเชื่อมต่อ และ edge มีอยู่ในกราฟ)
ตัวอย่าง
edges = [[0,2,100],[1,2,200],[1,3,100],[2,3,300]], a=0, b=2 → True
วิธีแก้ปัญหา
Cycle Property ของ MST:
- หา weight w ของ edge (a,b)
- สร้างกราฟย่อย: เฉพาะ edge ที่ weight < w
- ถ้า a และ b เชื่อมต่อกันในกราฟย่อยนี้ → (a,b) สร้าง cycle ที่มี edge หนักกว่า → ไม่อยู่ใน MST ใดๆ
- ถ้า a และ b ไม่เชื่อมต่อ → (a,b) เป็น lightest edge ข้าม cut → อยู่ใน MST บางตัว
- ใช้ DFS หา path ระหว่าง a และ b
โค้ด Python
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))
อินพุต
[[0,2,100],[1,2,200],[1,3,100],[2,3,300]], 0, 2
เอาต์พุต
True
