Поиск компонент связности

Компонента связности — это максимальное множество вершин, попарно достижимых друг из друга. Чтобы найти все компоненты в неориентированном графе, запускают обход (BFS или DFS) из каждой ещё не посещённой вершины.

Сложность: время O(V + E); память: O(V). Для динамического объединения множеств часто используют структуру система непересекающихся множеств (DSU / union-find).

def components(graph):
    seen = set()
    result = []
    for start in graph:
        if start in seen:
            continue
        stack, comp = [start], []
        while stack:
            v = stack.pop()
            if v in seen:
                continue
            seen.add(v)
            comp.append(v)
            stack.extend(graph[v])
        result.append(comp)
    return result