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

"ДРУЗЬЯ ДРУЗЕЙ" Условие: В компании из N человек известны пары друзей. Найти всех людей, которые находятся на расстоянии ровно 2 от человека A (друзья друзей, но не прямые друзья).

n, m, a = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

dist = [-1] * (n + 1)
queue = [a]
dist[a] = 0
idx = 0

while idx < len(queue):
    v = queue[idx]
    idx += 1
    for to in graph[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            queue.append(to)

friends_of_friends = []
for i in range(1, n + 1):
    if dist[i] == 2:
        friends_of_friends.append(i)

print("Друзья друзей человека", a, ":", friends_of_friends)

Загрузка...

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

💬

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

Печать