Разбор задачи «Восстановление связности спутниковой группировки»

Идея задачи

Нам дан неориентированный граф из n вершин и m рёбер. Каждая вершина — спутник, каждое ребро — работающий канал связи между двумя спутниками. Нужно определить, сколько новых соединений необходимо добавить, чтобы весь граф стал связным.

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

Ключевое наблюдение

Если граф распадается на k компонент связности, то минимальное количество рёбер, которое нужно добавить, равно:

k - 1

Почему именно так:

• одно новое ребро может соединить не более двух разных компонент;
• чтобы объединить k отдельных компонент в одну общую, нужно как минимум k - 1 соединение;
• этого количества всегда достаточно: можно просто последовательно соединить компоненты между собой.

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

Как посчитать компоненты связности

Есть два стандартных подхода:

1. DFS / BFS
2. DSU (система непересекающихся множеств, Disjoint Set Union)

Для этой задачи особенно удобно использовать DSU, потому что:

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

Что такое DSU

DSU хранит разбиение вершин на множества.

Поддерживаются две основные операции:

• find(x) — найти представителя множества, в котором находится вершина x;
• union(a, b) — объединить множества, содержащие a и b.

В начале каждая вершина находится в своей собственной компоненте, то есть всего компонент n.

Далее для каждого ребра (u, v):

• если u и v уже в одной компоненте, ничего не меняется;
• если в разных, объединяем их и уменьшаем число компонент на 1.

После обработки всех рёбер ответ будет равен:

components - 1

Почему петли и повторяющиеся рёбра не мешают

В условии возможны:

• петли u = v;
• повторяющиеся рёбра.

Это не проблема.

Петля

Ребро вида (u, u) не соединяет разные вершины и никак не влияет на связность.

Повторное ребро

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

Поэтому можно вообще не делать специальных проверок: DSU сам корректно обработает такие случаи.

Разберём пример

Пусть дан граф:

n = 6
рёбра:
1 - 2
2 - 3
4 - 5

Тогда компоненты такие:

• {1, 2, 3}
• {4, 5}
• {6}

Всего 3 компоненты.

Чтобы сделать граф связным, нужно добавить:

3 - 1 = 2

Например, можно соединить:

• вершину 3 с вершиной 4
• вершину 5 с вершиной 6

После этого весь граф станет одной компонентой.

Корректность решения

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

Утверждение 1

После обработки всех рёбер DSU разбивает вершины ровно на компоненты связности исходного графа.

Почему это верно:

• если между двумя вершинами есть путь, то все рёбра этого пути последовательно объединят их в одно множество;
• если две вершины оказались в одном множестве DSU, значит существовала цепочка объединений по рёбрам графа, то есть они действительно находятся в одной компоненте связности.

Следовательно, количество множеств в DSU после обработки всех рёбер равно количеству компонент связности графа.

Утверждение 2

Если в графе k компонент связности, то минимальное число новых рёбер, необходимое для связности, равно k - 1.

Почему это верно:

• каждое новое ребро может уменьшить число компонент не более чем на 1;
• чтобы из k компонент получить одну, нужно уменьшить их количество на k - 1, значит меньше рёбер быть не может;
• с другой стороны, можно выбрать по одной вершине из каждой компоненты и соединить компоненты в цепочку, используя ровно k - 1 ребро.

Значит, ответ действительно равен k - 1.

Так как DSU находит k, алгоритм корректен.

Оценка сложности

Пусть n — число вершин, m — число рёбер.

С DSU с эвристиками:

• сжатие путей;
• объединение по рангу.

получаем:

• время: O(m * α(n)), где α(n) — обратная функция Аккермана, которая на практике крайне мала;
• память: O(n).

Для ограничений задачи это решение работает эффективно.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, r;
    int comps;

    DSU(int n = 0) { init(n); }

    void init(int n) {
        p.resize(n + 1);
        r.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) p[i] = i;
        comps = n;
    }

    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        comps--;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    DSU dsu(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    cout << (dsu.comps - 1) << "\n";
    return 0;
}

Комментарий к реализации

• p[i] — родитель вершины i в DSU;
• r[i] — ранг дерева;
• comps — текущее число компонент;
• при каждом успешном объединении число компонент уменьшается на 1;
• в конце выводим comps - 1.

Реализация на Python

import sys
sys.setrecursionlimit(10**7)


class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
        self.components = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return False

        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra

        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1

        self.components -= 1
        return True



def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    dsu = DSU(n)

    for _ in range(m):
        u, v = map(int, input().split())
        dsu.union(u, v)

    print(dsu.components - 1)


if __name__ == "__main__":
    main()

Комментарий к реализации

Здесь логика полностью совпадает с C++-версией:

• в начале n компонент;
• каждое успешное объединение уменьшает их количество;
• ответ — components - 1.

Частые ошибки

1. Пытаться строить ответ напрямую по числу рёбер

Иногда кажется, что если рёбер мало, то ответ можно выразить через n и m. Это неверно.

Например:

• граф-цепочка из n вершин уже связен и имеет n - 1 ребро;
• другой граф с тем же количеством рёбер может быть несвязным.

Важно именно количество компонент связности, а не просто число рёбер.

2. Не учитывать, что граф неориентированный

Ребро (u, v) означает двустороннюю связь. В DSU это естественно учитывается, потому что мы просто объединяем вершины в одно множество.

3. Пытаться отдельно фильтровать петли и дубликаты

Это не ошибка, но и не необходимость. DSU сам безопасно обрабатывает такие случаи.

4. Ошибка с индексацией

Вершины в условии нумеруются с 1 до n, поэтому массивы DSU удобно делать размера n + 1.

Альтернативный подход: DFS / BFS

Можно было бы решить задачу и через обход графа:

1. построить список смежности;
2. запускать DFS/BFS из каждой непосещённой вершины;
3. число запусков и будет количеством компонент.

Тогда ответ снова равен components - 1.

Однако DSU здесь выглядит особенно естественно, потому что:

• не нужно хранить полный список смежности в удобной для обхода форме;
• обработка идёт прямо по входным рёбрам;
• код получается компактным и быстрым.