Статья Автор: Алексеева Варвара

dfs

def dfs(start):
    # добавляем текущую вершину в порядок обхода
    order.append(start)
    # помечаем как посещённую
    visited[start] = True
    
    # перебираем соседей в порядке возрастания
    for neighbor in sorted(V[start]):
        if not visited[neighbor]:
            dfs(neighbor)

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

# список смежности (используем set для уникальности, потом отсортируем)
V = [set() for _ in range(n + 1)]

# читаем рёбра (неориентированный граф)
for _ in range(m):
    u, v = map(int, input().split())
    V[u].add(v)
    V[v].add(u)

# массив посещённых вершин
visited = [False] * (n + 1)

# список для хранения порядка обхода
order = []

# запускаем DFS из стартовой вершины
dfs(s)

# проверяем, все ли вершины посещены
if len(order) == n:
    print(*order)
else:
    print("НЕТ")

Загрузка...

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

💬

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

Печать