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

"ПРОВЕРКА СВЯЗНОСТИ ГРАФА" Условие: Проверить, является ли граф связным (можно ли из любой вершины добраться до любой другой).

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

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

visited = [False] * (n + 1)
queue = [1]
visited[1] = True
idx = 0
count = 1

while idx < len(queue):
    v = queue[idx]
    idx += 1
    for to in graph[v]:
        if not visited[to]:
            visited[to] = True
            count += 1
            queue.append(to)

if count == n:
    print("Граф связный")
else:
    print("Граф несвязный, достижимо только", count, "вершин из", n)

Загрузка...

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

💬

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

Печать