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

3 - Социальная сеть

def dfs(graph, 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 = []
            for i in range(n):
                if graph[v][i] == 1:
                    neighbors.append(i)
            
            # Сортируем по возрастанию и добавляем в стек в обратном порядке
            for nxt in sorted(neighbors, reverse=True):
                if not visited[nxt]:
                    stack.append(nxt)
    
    return order, visited

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

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

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

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

Загрузка...

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

💬

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

Печать