Chương trình kiểm tra tồn tại đường đi giới hạn độ dài cạnh trong Python

Mô tả bài toán

Cho đồ thị vô hướng có trọng số n đỉnh, danh sách cạnh edgeList[u,v,w]. Truy vấn queries[i] = (p,q,lim): có đường đi từ p đến q với mọi cạnh trọng số < lim không? Trả về mảng True/False.

Ví dụ

Đồ thị 4 đỉnh, cạnh: (1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3). Truy vấn: (1,4,12)->True, (2,3,3)->False, (1,2,15)->True.

Giải thuật (Union-Find Offline)

1. Sắp xếp edgeList theo trọng số, queries theo lim.
2. Duyệt truy vấn theo lim tăng: union các cạnh có trọng số < lim.
3. Kiểm tra find(p) == find(q).

Triển khai Python

def solve(n, edgeList, queries):
    parent = [i for i in range(n + 1)]
    rank = [0] * (n + 1)
    def find(parent, x):
        if parent[x] == x:
            return x
        parent[x] = find(parent, parent[x])
        return parent[x]
    def union(parent, a, b):
        a = find(parent, a)
        b = find(parent, b)
        if a == b: return
        if rank[a] < rank[b]:
            parent[a] = b
        elif rank[a] > rank[b]:
            parent[b] = a
        else:
            parent[b] = a
            rank[a] += 1
    edgeList.sort(key=lambda x: x[2])
    res = [0] * len(queries)
    queries = [[i, ch] for i, ch in enumerate(queries)]
    queries.sort(key=lambda x: x[1][2])
    ind = 0
    for i, (a, b, w) in queries:
        while ind < len(edgeList) and edgeList[ind][2] < w:
            union(parent, edgeList[ind][0], edgeList[ind][1])
            ind += 1
        res[i] = find(parent, a) == find(parent, b)
    return res

n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries))

Đầu vào

4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)], [(1,4,12),(2,3,3),(1,2,15)]

Đầu ra

[True, False, True]