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

3 - Бэтмен

def dfs(adj_list, start, n):
    visited = [False] * n
    order = []
    stack = [start]
    
    while stack:
        v = stack.pop()
        if not visited[v]:
            order.append(v + 1)
            visited[v] = True
            
            # Получаем соседей текущей зоны
            neighbors = adj_list[v]
            # Сортируем по возрастанию и добавляем в стек в обратном порядке
            for nxt in sorted(neighbors, reverse=True):
                if not visited[nxt]:
                    stack.append(nxt)
    
    return order, visited

# Чтение входных данных
n, m, s = map(int, input().split())

# Создаем список смежности
adj_list = [[] for _ in range(n)]

# Читаем M переходов
for _ in range(m):
    a, b = map(int, input().split())
    # Переводим в 0-индексацию
    a -= 1
    b -= 1
    # Добавляем связи в обе стороны (переходы двусторонние)
    adj_list[a].append(b)
    adj_list[b].append(a)

# Сортируем списки смежности для каждой зоны
for i in range(n):
    adj_list[i].sort()

# Запуск DFS
order, visited = dfs(adj_list, s - 1, n)

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

Загрузка...

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

💬

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

Печать