โปรแกรมตรวจสอบ Vertex ใน Undirected Graph มี Path ต่ำกว่ากำหนดหรือไม่ใน Python

ปัญหา

กราฟ Undirected มีน้ำหนัก Query(p, q, limit): มี Path จาก p ไป q ที่ Cost < limit หรือไม่ (≤ limit ก็ได้)

ตัวอย่าง

Graph: Edges กับ Weights

Queries: (0,2,10)→False, (3,1,30)→True, (4,3,30)→True

อัลกอริทึม (Offline + Union-Find + Sort)

เรียง Edges ตาม Weight
1. สร้าง Union-Find แบบ Persistent: บันทึก Parent Array ทุกครั้งที่ Weight เปลี่ยน
2. สำหรับ Query(limit): Binary Search หา Index ของ Weight < limit
3. ใช้ Union-Find Snapshot นั้น ตรวจสอบ Connected(p, q)

ตัวอย่างโค้ด

import bisect

class Solution:
    def __init__(self, n, edgeList):
        def find(node):
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]
        def union(x, y):
            parent[find(y)] = find(x)
        
        parent = {i: i for i in range(n)}
        edgeList.sort(key=lambda x: x[2])
        
        self.connections = []
        self.weights = []
        
        for index, (i, j, weight) in enumerate(edgeList):
            union(i, j)
            # บันทึก Snapshot เฉพาะเมื่อ Weight เปลี่ยน
            if index != len(edgeList) - 1 and weight == edgeList[index + 1][2]:
                continue
            self.weights.append(weight)
            self.connections.append([find(i) for i in parent])
    
    def query(self, p, q, limit):
        index = bisect.bisect_left(self.weights, limit)
        if index == 0:
            return False
        return self.connections[index - 1][p] == self.connections[index - 1][q]

# Test
ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))  # False
print(ob.query(3, 1, 30))  # True
print(ob.query(4, 3, 30))  # True

ความซับซ้อน

• Preprocess: O(E log E + E × α(V))
• Query: O(log E) (Binary Search)
• Space: O(E × V) สำหรับ Snapshots (Optimize ได้ด้วย Persistent Union-Find)