สมมติว่าเรามีกราฟ acyclic กำกับ โดยมีจุดยอด n จุดและโหนดมีหมายเลขตั้งแต่ 0 ถึง n-1 กราฟจะแสดงด้วยรายการขอบ โดยที่ edge[i] =(u, v) แทนขอบตรงจากโหนด u ถึง โหนด v. เราต้องหาจุดยอดที่เล็กที่สุดที่โหนดทั้งหมดในกราฟสามารถเข้าถึงได้ (เราสามารถคืนจุดยอดในลำดับใดก็ได้)
ดังนั้นหากอินพุตเป็นแบบ
ผลลัพธ์จะเป็น [0,2,3] เนื่องจากจุดยอดทั้งสองนี้ไม่สามารถเข้าถึงได้จากจุดยอดอื่น ดังนั้นหากเราเริ่มจากจุดยอดเหล่านี้ เราก็สามารถครอบคลุมได้ทั้งหมด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของขอบ
-
all_nodes :=ชุดใหม่จากช่วง 0 ถึง n
-
v :=ชุดใหม่
-
สำหรับแต่ละขอบ (i, j) ในขอบ ทำ
-
เพิ่ม j ลงใน v
-
-
ans :=ลบขอบทั่วไปทั้งหมดออกจาก all_nodes และ v ออกจาก all_nodes
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(edges): n = len(edges) all_nodes = set(range(n)) v = set() for edge in edges: v.add(edge[1]) ans = all_nodes - v return ans edges = [(0,1),(2,1),(3,1),(1,4),(2,4)] print(solve(edges))
อินพุต
[(0,1),(2,1),(3,1),(1,4),(2,4)]
ผลลัพธ์
{0, 2, 3} 