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

3 - Minecraft

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())

# Чтение матрицы инцидентности (N x M)
matrix = []
for i in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

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

# Проходим по каждому мосту (столбцу)
for bridge in range(m):
    # Находим два острова, которые соединяет этот мост
    islands = []
    for island in range(n):
        if matrix[island][bridge] == 1:
            islands.append(island)
    
    # Если найдено ровно 2 острова (мост соединяет два острова)
    if len(islands) == 2:
        a, b = islands
        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("НЕТ")

Загрузка...

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

💬

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

Печать