Статья Автор: Дубинин Дмитрий

3 - Марио

def dfs(g, v0):
    visited = [False] * len(g)
    order = []
    stack = [v0]
    while stack:
        v = stack.pop()
        if not visited[v]:
            order.append(v + 1)  # добавляем номер комнаты (1-based)
            visited[v] = True
            # обходим соседей в порядке возрастания, поэтому добавляем в обратном порядке
            for nxt in sorted(g[v], reverse=True):
                stack.append(nxt)
    return order, visited

# чтение входных данных
n, s = map(int, input().split())
g = []

# заполняем граф
for i in range(n):
    line = input().strip()
    if line:  # если строка не пустая
        neighbors = list(map(int, line.split()))
        neighbors.sort()  # сортируем для порядка обхода
        # переводим в 0-based индексацию
        g.append([x - 1 for x in neighbors])
    else:
        g.append([])

# запускаем DFS
order, visited = dfs(g, s - 1)

# проверяем, посетили ли все комнаты
if all(visited):
    print(' '.join(map(str, order)))
else:
    print("НЕТ")

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать