جواب «Build Order» چالش 12 از جلسهی 35
سؤال
ورودی وابستگیهای بستهها به شکل <a> <b> (یعنی a باید قبل از b ساخته شود) تا end. ترتیب ساخت را با الگوریتم Kahn (BFS روی درجهی ورودی) پیدا کنید؛ هر بار از بین گرههای آماده، الفباییترین را بردارید (از heapq استفاده کنید). ترتیب را با فاصله چاپ کنید، یا اگر چرخه وجود داشت cycle detected.
راهنما
indegree هر گره را بشمارید؛ گرههای با درجهی صفر آمادهاند. اگر در پایان همهی گرهها خارج نشدند، چرخه هست.
یک جواب درست
import heapq
from collections import defaultdict
graph = defaultdict(list)
indegree = {}
while True:
line = input()
if line == "end":
break
a, b = line.split()
graph[a].append(b)
indegree.setdefault(a, 0)
indegree[b] = indegree.get(b, 0) + 1
ready = [n for n, d in indegree.items() if d == 0]
heapq.heapify(ready)
order = []
while ready:
node = heapq.heappop(ready)
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
heapq.heappush(ready, nxt)
print(" ".join(order) if len(order) == len(indegree) else "cycle detected")
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن