Cho đồ thị n đỉnh 0..n-1, vô hướng, cạnh có trọng số 1,2,3. Jack đi được cạnh trọng số 1, Casey đi được 2, cả hai đi được 3. Xóa cạnh để đồ thị liên thông cho cả Jack và Casey. Trả về số cạnh xóa, hoặc -1 nếu không thể.
Ví dụ: n=5, đầu ra = -1 (không thể làm liên thông cho cả hai).
Giải pháp
Union-Find (DSU) xử lý 3 loại cạnh theo thứ tự ưu tiên:
- Định nghĩa find(val) với path compression
- Định nghĩa union(val1, val2): trả về 1 nếu gộp thành công, 0 nếu đã cùng tập
- res := 0, edge1 := 0, edge2 := 0
- root := [0..n]
- Xử lý cạnh loại 3 (cả hai): union, tăng edge1,edge2 nếu thành công, ngược lại res++
- Lưu root0 := root[:]
- Xử lý cạnh loại 1 (Jack): union trên root0, tăng edge1 hoặc res++
- Khôi phục root := root0
- Xử lý cạnh loại 2 (Casey): union, tăng edge2 hoặc res++
- Trả về res nếu edge1 == edge2 == n-1, ngược lại -1
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
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)]))
Đầu vào
5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]
Đầu ra
-1