Try It in Python: Count the Groups چالش 7 از جلسهی 36، سخت
«با پایتون امتحان کن» (اختیاری). خطِ اول n است و خطِ دوم line (شهرهای ۱ تا n پشتِ سرِ هم در یک خط) یا star (شهرِ ۱ به همهی شهرها جاده دارد). با امتحانِ همهی گروهها بشمار چند گروهِ بههمپیوسته هست و چاپ کن.
تابعِ connected(group) آماده است؛ تو فقط همهی گروهها را بساز. راه: عددهای 1 تا 2 ** n - 1 را بشمار؛ بیتِ k اُمِ عدد یعنی شهرِ k + 1 در گروه هست.
با 4 و line باید 10 چاپ شود.
n = int(input())
shape = input()
if shape == "line":
roads = [(k, k + 1) for k in range(1, n)]
else:
roads = [(1, k) for k in range(2, n + 1)]
def connected(group):
start = min(group)
seen = {start}
stack = [start]
while stack:
v = stack.pop()
for a, b in roads:
for x, y in ((a, b), (b, a)):
if x == v and y in group and y not in seen:
seen.add(y)
stack.append(y)
return seen == group
count = 0
# try every group of towns here
print(count)
راهنما و جواب این چالش · برگشت به درس جلسهی 36: شهرهای بههمپیوسته
بیشتر بخوان: list comprehension در پایتون: از حلقه for تا یک خط کد