بتل کد Battle Codeدارد باز می‌شود…

جواب «Connected Components» چالش 10 از جلسه‌ی 35

سؤال

خط اول تعداد سرورها n است (شماره‌ها 0 تا n-1). خطوط بعدی اتصال‌ها <a> <b> تا end. با BFS از هر گره‌ی بازدیدنشده، مؤلفه‌های همبند را پیدا کنید و چاپ کنید components: <تعداد> و در خط بعد اندازه‌ی مؤلفه‌ها به ترتیب نزولی با فاصله.

راهنما

روی همه‌ی گره‌ها حلقه بزنید؛ هر بار که به گره‌ی بازدیدنشده رسیدید یک BFS جدید یعنی یک مؤلفه‌ی جدید.

یک جواب درست

from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
while True:
    line = input()
    if line == "end":
        break
    a, b = map(int, line.split())
    graph[a].append(b)
    graph[b].append(a)
seen = [False] * n
sizes = []
for s in range(n):
    if seen[s]:
        continue
    seen[s] = True
    queue = deque([s])
    size = 0
    while queue:
        node = queue.popleft()
        size += 1
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                queue.append(nxt)
    sizes.append(size)
print(f"components: {len(sizes)}")
print(*sorted(sizes, reverse=True))

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن