โปรแกรมตรวจสอบว่ากราฟเดินทางได้โดยทุกคนใน Python

สมมติว่าเราได้รับกราฟที่มี n จุดยอดตั้งชื่อ 0 ถึง n-1 กราฟเป็นแบบไม่มีทิศทางและแต่ละเส้นขอบมีน้ำหนัก กราฟสามารถมีน้ำหนัก 3 ประเภท และแต่ละน้ำหนักหมายถึงภารกิจเฉพาะ มีสองคนที่สามารถเดินทางในกราฟได้ คือ Jack และ Casey Jack เดินทางได้ถ้าน้ำหนักเส้นขอบเป็น 1 Casey เดินทางได้ถ้าเป็น 2 และทั้งคู่เดินทางได้ถ้าเป็น 3 เราต้องลบเส้นขอบที่จำเป็นเพื่อให้กราฟเดินทางได้สำหรับทั้ง Jack และ Casey ส่งคืนจำนวนเส้นขอบที่ต้องลบเพื่อให้กราฟเดินทางได้ หรือ -1 ถ้าไม่สามารถทำได้

เช่น ถ้าอินพุตเป็นดังภาพและ n = 5 ผลลัพธ์จะเป็น -1 กราฟไม่สามารถทำให้เดินทางได้สำหรับทั้งคู่โดยการลบเส้นขอบ คำตอบคือ -1

วิธีแก้ปัญหา

• กำหนดฟังก์ชัน find() รับ val:
  • ถ้า val ไม่เท่ากับ root[val]: root[val] := find(root[val])
  • return root[val]
• กำหนดฟังก์ชัน union() รับ val1, val2:
  • val1 := find(val1), val2 := find(val2)
  • ถ้า val1 เท่ากับ val2: return 0
  • root[val1] := val2
  • return 1
• res := 0, edge1 := 0, edge2 := 0
• root := รายการใหม่จาก range 0 ถึง n + 1
• สำหรับแต่ละเส้นขอบ (u, v) และน้ำหนัก w ใน e:
  • ถ้า u เท่ากับ 3:
    • ถ้า union(v, w) ไม่เป็นศูนย์: edge1 := edge1 + 1, edge2 := edge2 + 1
    • มิฉะนั้น: res := res + 1
• root0 := root[จากดัชนี 0 ถึงสุด]
• สำหรับแต่ละเส้นขอบ (u, v) และน้ำหนัก w ใน e:
  • ถ้า u เท่ากับ 1:
    • ถ้า union(v, w) ไม่เป็นศูนย์: edge1 := edge1 + 1
    • มิฉะนั้น: res := res + 1
• root := root0
• สำหรับแต่ละเส้นขอบ (u, v) และน้ำหนัก w ใน e:
  • ถ้า u เท่ากับ 2:
    • ถ้า union(v, w) ไม่เป็นศูนย์: edge2 := edge2 + 1
    • มิฉะนั้น: res := res + 1
• return res ถ้า edge1 เท่ากับ edge2 เท่ากับ n - 1 มิฉะนั้น return -1

ตัวอย่าง

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)]))

อินพุต

Input: 5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]

เอาต์พุต

-1