डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं।
एल्गोरिदम
- सभी नोड्स का सेट बनाएं (0 से n-1)।
- सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं।
- सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)।
- यही मिनिमम वर्टेक्स सेट है।
उदाहरण कोड
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)] -> {0,2,3}
इनपुट/आउटपुट
इनपुट: [(0,1),(2,1),(3,1),(1,4),(2,4)]
आउटपुट: {0, 2, 3}