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

КОМПОНЕНТЫ СВЯЗНОСТИ

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)
components = []

for v in range(1, n + 1):
    if not visited[v]:
        stack = [v]
        visited[v] = True
        component = [v]
        
        while stack:
            current = stack.pop()
            for to in graph[current]:
                if not visited[to]:
                    visited[to] = True
                    component.append(to)
                    stack.append(to)
        
        components.append(component)

print("Количество компонент:", len(components))
print("Компоненты:", components)

Загрузка...

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

💬

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

Печать