Giả sử, chúng ta được cho một đồ thị có chứa n đỉnh được đánh số từ 0 đến n - 1. Đồ thị là vô hướng và mỗi cạnh có một trọng số. Biểu đồ có thể có ba loại trọng số và mỗi trọng số biểu thị một nhiệm vụ cụ thể. Có hai người có thể đi ngang qua biểu đồ, đó là Jack và Casey. Jack có thể đi ngang qua biểu đồ nếu một cạnh có trọng số 1, Casey có thể đi ngang qua biểu đồ nếu nó có trọng số 2 và cả hai đều có thể đi ngang qua biểu đồ nếu nó có trọng số cạnh 3. Chúng ta phải loại bỏ bất kỳ cạnh nào cần thiết để làm cho biểu đồ có thể duyệt được cho cả hai. Jack và Casey. Chúng tôi trả về số cạnh cần loại bỏ để làm cho biểu đồ có thể duyệt được hoặc chúng tôi trả về -1 nếu nó không thể di chuyển được.
Vì vậy, nếu đầu vào giống như
và n =5; thì đầu ra sẽ là -1
Không thể làm cho biểu đồ có thể duyệt được cho cả hai bằng cách loại bỏ một cạnh. Vì vậy, câu trả lời là -1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm find (). Điều này sẽ mất giá trị
-
nếu val không giống với gốc [val] thì
-
root [val]:=find (root [val])
-
-
trả về gốc [val]
-
-
Định nghĩa một hàm union (). Điều này sẽ lấy val1, val2
-
val1:=find (val1)
-
val2:=find (val2)
-
nếu val1 giống val2 thì
-
trả về 0
-
-
root [val1]:=val2
-
trả lại 1
-
-
res:=0
-
edge1:=0
-
edge2:=0
-
root:=một danh sách mới từ phạm vi 0 đến n + 1
-
đối với mỗi cạnh (u, v) và trọng lượng của nó là w tính bằng e, thực hiện
-
nếu bạn giống với 3, thì
-
nếu union (v, w) khác 0 thì
-
edge1:=edge1 + 1
-
edge2:=edge2 + 1
-
-
nếu không,
-
res:=res + 1
-
-
-
-
root0:=root [từ chỉ mục 0 đến cuối]
-
đối với mỗi cạnh (u, v) và trọng lượng của nó là w tính bằng e, thực hiện
-
nếu bạn giống với 1, thì
-
nếu union (v, w) khác 0 thì
-
edge1:=edge1 + 1
-
-
nếu không,
-
res:=res + 1
-
-
-
-
root:=root0
-
đối với mỗi cạnh (u, v) và trọng lượng của nó là w tính bằng e, thực hiện
-
nếu u giống với 2, thì
-
nếu union (v, w) khác 0 thì
-
edge2:=edge2 + 1
-
-
nếu không,
-
res:=res + 1
-
-
-
-
trả về res nếu edge1 giống edge2 và n - 1
-
nếu không, trả về -1
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
def giải (n, e):def find (val):if val! =root [val]:root [val] =find (root [val]) trả về 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 trong 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 trả về res nếu edge1 ==edge2 ==n - 1 else -1print (giải quyết (5, [(0,1,1), (1,2,2), (2, 3,3), (3,4,1), (4,0,2)]))
Đầu vào
Đầu vào:5, [(0,1,1), (1,2,2), (2,3,3), (3,4,1), (4,0,2)]Đầu ra
-1