โปรแกรมหาชุดโหนดน้อยที่สุดเพื่อถึงทุกโหนดใน DAG ด้วย Python

ใน Directed Acyclic Graph (DAG) หาโหนดที่ไม่มี incoming edges (in-degree = 0) เพราะโหนดเหล่านี้ไม่สามารถเข้าถึงได้จากโหนดอื่น ต้องเริ่มจากโหนดเหล่านี้จึงจะถึงทุกโหนด ใช้ set difference: all_nodes - nodes_with_incoming_edges

ขั้นตอนการทำงาน

1. all_nodes = set(0..n-1)
2. v = set() เก็บโหนดที่มี incoming edge (destination ของ edges)
3. วนลูป edges เพิ่ม edge[1] เข้า v
4. ans = all_nodes - v
5. คืน ans

ตัวอย่างโค้ด

def solve(edges):
    n = len(edges)  # Note: n should be number of vertices, not edges count
    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))  # Output: {0, 2, 3}

อินพุต/เอาต์พุต

Input: [(0,1),(2,1),(3,1),(1,4),(2,4)]
Output: {0, 2, 3}

หมายเหตุ: n ในโค้ดต้นฉบับใช้ len(edges) ซึ่งอาจไม่ถูกต้องถ้าจำนวน vertices != จำนวน edges ควรส่ง n เข้ามาแยกต่างหาก