Пошук компонент зв'язності у графі

Дано неорієнтований граф $G$ з $n$ вершинами і $m$ ребрами. Потрібно знайти у ньому всі компоненти зв'язності, тобто розбити вершини графа на декілька груп так, щоб всередині кожної групи можна було дійти від кожної вершини в групі до будь-якої іншої в тій же групі, а між різними группами - шляхів не існувало.

Алгоритм

Для розв'язку можна скористатися як пошуком в глибину, так і пошуком в ширину.

Фактично, ми будемо проводити серію обходів: спочатку запустимо обхід з першої вершини, і всі вершини, які він при цьому обійшов - утворюють першу компоненту зв'язності. Потім найдемо першу вершину з тих, які ще не були відвідані, і запустимо обхід з неї, знайшовши тим самим одному компоненту зв'язності. І так далі, поки всі вершини не стануть відвіданими.

Підсумкова асимптотика складе $O(n + m)$: насправді, такий алгоритм не буде запускаться від однієї і тією ж вершини двічі, а, значить, кожне ребро буде переглянуто рівне два рази (з одного кінця і з іншого кінця).

Реалізація

Для реалізації трішки більш зручним є обхід в глибину:

void find_connected_components_dfs(int v,
                                   const vector<vector<int>>& g,
                                   vector<bool>& visited,
                                   vector<int>& component) {
    visited[v] = true;
    component.push_back(v);
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (!visited[to]) {
            find_connected_components_dfs(to, g, visited, component);
        }
    }
}

vector<vector<int>> find_connected_components(const vector<vector<int>>& g) {
    int n = g.size(); // кількість вершин
    vector<bool> visited(n); // відвідані вершини
    vector<vector<int>> components; // знайдені компоненти зв'язності

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components.emplace_back(); // додаємо нову пусту компоненту в кінець масиву
            find_connected_components_dfs(i, g, visited, components.back());
        }
    }
    return components;
}

Застосування

TODO: add applications

Задачі

TODO: add problems