Разбор задачи «Разрозненные острова»

1. Идея

Нужно найти количество групп островов, внутри которых из любого острова можно добраться в любой другой, а между разными группами пути нет.

В терминах графов:

• острова — это вершины;
• лодочные маршруты — это рёбра;
• так как маршрут двусторонний, граф неориентированный.

Тогда задача сводится к поиску количества компонент связности в неориентированном графе.

Для этого будем запускать обход графа из каждой ещё не посещённой вершины. Каждый такой запуск находит ровно одну компоненту связности.

2. Наблюдения

1. Если начать обход из некоторого острова, то мы посетим все острова, до которых можно добраться по маршрутам.
2. Все такие острова принадлежат одной компоненте связности.
3. Если после этого выбрать другой ещё не посещённый остров, то он точно лежит в другой компоненте.
4. Значит, число запусков обхода и будет ответом.

В эталонном решении используется обход в глубину без рекурсии — через собственный стек. Это важно, потому что при n до 100000 рекурсивный DFS может привести к переполнению стека вызовов.

3. Алгоритм

1. Считываем n и m.
2. Строим список смежности g, где g[v] — список островов, связанных с островом v.
3. Создаём массив used, который хранит, посещён ли остров.
4. Перебираем все острова от 1 до n:
   • если остров уже посещён, пропускаем его;
   • иначе нашли новую компоненту, увеличиваем счётчик components;
   • запускаем DFS с помощью стека:
     • кладём стартовый остров в стек;
     • помечаем его как посещённый;
     • пока стек не пуст:
       • извлекаем вершину;
       • просматриваем всех соседей;
       • если сосед ещё не посещён, помечаем его и кладём в стек.
5. После завершения перебора выводим components.

4. Почему это работает

Докажем, что алгоритм действительно считает количество компонент связности.

Рассмотрим момент, когда внешний цикл дошёл до острова start.

Случай 1: start уже посещён

Это значит, что ранее мы уже запускали обход из некоторого острова той же компоненты связности и дошли до start. Значит, новая компонента здесь не начинается.

Случай 2: start ещё не посещён

Тогда этот остров не был достигнут ни из одного ранее обработанного старта, то есть он лежит в новой компоненте связности.

После этого запускается DFS:

• он проходит по всем маршрутам, достижимым из start;
• значит, посещает все острова из той же компоненты;
• и не может выйти за пределы компоненты, потому что между разными компонентами нет рёбер.

Следовательно:

• каждый запуск DFS соответствует ровно одной новой компоненте;
• каждая компонента будет найдена ровно один раз.

Значит, число запусков DFS равно числу компонент связности, что и требуется.

5. Сложность

Пусть n — число островов, m — число маршрутов.

Время

• построение графа: O(m);
• обход всех вершин и рёбер: O(n + m).

Итоговая сложность: O(n + m).

Память

• список смежности хранит все рёбра: O(n + m);
• массив посещения: O(n);
• стек обхода: O(n) в худшем случае.

Итоговая память: O(n + m).

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<bool> used(n + 1, false);
    int components = 0;

    for (int start = 1; start <= n; start++) {
        if (used[start]) continue;

        components++;
        vector<int> st;
        st.push_back(start);
        used[start] = true;

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();

            for (int to : g[v]) {
                if (!used[to]) {
                    used[to] = true;
                    st.push_back(to);
                }
            }
        }
    }

    cout << components << "\n";
    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

used = [False] * (n + 1)
components = 0

for start in range(1, n + 1):
    if used[start]:
        continue

    components += 1
    stack = [start]
    used[start] = True

    while stack:
        v = stack.pop()
        for to in g[v]:
            if not used[to]:
                used[to] = True
                stack.append(to)

print(components)