جواب «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))
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن