2316. Подсчет недостижимой пары узлов в неориентированном графе (Count Unreachable Pairs of Nodes in an Undirected Graph)

Задание.

Дано целое число n. Существует неориентированный граф с n узлами, пронумерованными от 0 до n - 1.

Также даётся двумерный целочисленный массив edges, где edges[i] = [a_i, b_i] обозначают, что существует неориентированное ребро, соединяющее узлы a_i и b_i/

Верните количество пар различных узлов, которые недоступны друг для друга.

Пример 1.

Входные данные: n = 3, edges = [ [0,1], [0,2], [1,2] ]

Результат: 0

Пояснение: Нет пар узлов, которые были бы недоступны друг для друга. Следовательно, мы возвращаем 0.

Пример 2.

Входные данные: n = 7, edges = [ [0,2], [0,5], [2,4], [1,6], [5,4]]

Результат: 14

Пояснение: Существует 14 пар узлов, которые недоступны друг для друга: [ [0,1], [0,3], [0,6], [1,2], [1,3], [1,4], [1,5], [2,3], [2,6], [3,4], [3,5], [3,6], [4,6], [5,6] ]. Следовательно, мы возвращаем 14.

Решение.

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        
    }
};

Способ решения.

Обзор

У нас есть неориентированный граф с n узлами, пронумерованными от 0 до n - 1.

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

Способ решения 1. Dfs. Обход графа в глубину.

Интуиция.

Как известно, связный компонент неориентированного графа – это подграф, в котором каждая пара узлов соединена друг с другом неким путем. Это означает, что узлы в соединенном компоненте могут достигать всех других узлов в том же соединенном компоненте.

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

Давайте вернемся ко второму примеру из постановки задачи.

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

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

Общее количество пар узлов с одним узлом в первом компоненте и другим узлом в любом из оставшихся компонентов будет равно количеству узлов в первом компоненте, умноженному на общее количество узлов, за исключением узлов первого компонента, т.е. 4 * (7 - 4) = 12 пар. Это означает, что существует 12 пар узлов, которые недоступны друг от друга, где один из двух узлов находится в первом компоненте.

Давайте перейдем ко второму компоненту, который имеет только один узел. Таким образом, количество недостижимых пар узлов с одним узлом во втором компоненте будет равно общему количеству узлов во втором компоненте, умноженному на общее количество узлов, кроме текущего компонента и первого компонента (мы уже рассмотрели пары, сформированные с использованием узлов в первом компоненте). Это так 1 * (7 - 4 - 1) = 2 пары.

Теперь мы рассмотрели все пары, сформированные с одним узлом в первом компоненте, а также все пары, сформированные с одним узлом во втором компоненте. Поскольку у нас остался только третий компонент, больше не может быть сформировано пар недостижимых узлов. Общее количество необходимых пар равно 12 + 2 = 14.

Итак, чтобы найти общее количество пар, которые недоступны друг от друга, мы должны выполнить итерацию по графику и определить размер каждого компонента. Затем мы умножаем количество узлов в текущем компоненте на общее количество узлов в графике, игнорируя узлы в текущем компоненте и ранее посещенные компоненты (мы уже рассмотрели пары узлов, сформированных с одним из узлов в предыдущих компонентах). Чтобы получить требуемый ответ, мы добавляем это количество пар узлов, перебирая все компоненты один за другим, как рассчитано в предыдущем примере.

Для определения количества узлов в каждом компоненте можно использовать поиск в глубину (DFS).

В DFS мы используем рекурсивную функцию для исследования узлов как можно дальше вдоль каждой ветви. Дойдя до конца ветви, мы возвращаемся к исходному узлу и продолжаем исследовать следующие ветви.

Как только мы столкиваемся с нерассмотренным узлом, мы берём в рассмотрение один из его соседних узлов (если он существует) в качестве следующего узла в этой ветви. Рекурсивно вызываем функцию, чтобы взять следующий узел в качестве “начального узла”, чтобы решить подзадачу.

Алгоритм.

1. Создаём список соседей, где adj[X] содержит всех соседей узла X.

2. Для подсчёта количества недоступных пар узлов объявляем переменную numberOfPairs. Инициализируем нулём (0).

3. Для хранения количества узлов в текущем компоненте объявляем переменную sizeOfComponent. Инициализируем нулём (0).

4. Для отслеживания количества непросмотренных узлов графа после обхода DFS объявляем переменную remainingNodes. Инициализируем n.

5. Для отслеживания просмотренных узлов объявляем массив visit размером n элементов.

6. Выполняем итерацию по всем узлам, и для каждого узла проверяем, посещен он или нет. Если узел i не посещен, начинаем обход DFS:

• Для обхода дерева используется функция dfs. Для каждого вызова передаются параметрами node, adj и visit. Обход начинается с узла i.

• Узел помечается, как посещенный. Объявляется переменная count для отслеживания количества узлов в этом компоненте. Сount инициализируется единицей (1), чтобы подсчитать сам узел.

• Выполняется итерация по всем соседям узла. Если соседний узел был ещё не посещён, выполняется рекурсивный вызов dfs, а соседний узел передаётся в качестве параметра node. Для данного вызова dfs производится подсчет количества посещённых узлов и добавляется к общему значению переменной count.

• После выполнения итераций для соседних узлов count возвращается, и его значение запоминается в sizeOfComponent.

• Количество недостижимых пар узлов с одним узлом в текущем компоненте и другим узлом в любом другом компоненте, кроме текущего компонента и ранее посещенных компонентов, равно sizeOfComponent * (remainingNodes - sizeOfComponent). Оно добавляется к numberOfPairs.

• Переменная remainingNodes уменьшается на sizeOfComponent, потому что мы добавили все необходимые пары узлов, причем один из узлов находится в текущем компоненте, и мы не хотим добавлять их снова. В результате мы предполагаем, что их больше нет.

7. Возвращаем numberOfPairs

Реализация.

class Solution {
public:
    int dfs(int node, vector<vector<int>>& adj, vector<bool>& visit) {
        int count = 1;
        visit[node] = true;
        for (int neighbor : adj[node]) {
            if (!visit[neighbor]) {
                count += dfs(neighbor, adj, visit);
            }
        }
        return count;
    }

    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        long long numberOfPairs = 0;
        long long sizeOfComponent = 0;
        long long remainingNodes = n;
        vector<bool> visit(n);
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                sizeOfComponent = dfs(i, adj, visit);
                numberOfPairs += sizeOfComponent * (remainingNodes - sizeOfComponent);
                remainingNodes -= sizeOfComponent;
            }
        }
        return numberOfPairs;
    }
};

Анализ сложности.

У нас n – количество узлов, а e – количество рёбер.

• Сложность по времени: O(n+e)

  • Необходимо O(e) времени для инициализации списка соседей и O(n) времени для инициализации массива visit.

  • Функция dfs посещает каждый узел один раз, что занимает в общей сложности O(n) времени. Поскольку у нас есть неориентированные ребра, каждое ребро может быть повторено только дважды (по узлам в конце), что приводит к общему количеству операций O(e) при посещении всех узлов.

  • В результате общее требуемое время составляет O(n+e)

• Сложность по памяти: O(n+e)

  • Построение списка смежности занимает O(e) памяти.

  • Массив visit занимает O(n) памяти.

  • При рекурсивных вызовах функции dfs используется стек, который в наихудшем сценарии необходим для n элементов. В этом случае это заняло бы O(n) памяти.

Способ решения 2. Bfs. Обход графа в ширину.

Интуиция.

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

BFS – это алгоритм обхода или поиска по графу. Он проходит по уровням, т.е. исследуются все узлы на текущем уровне (скажем, l), прежде чем переходить к узлам на следующем уровне (l + 1), где номер уровня – это расстояние от начального узла. BFS реализуется с помощью очереди.

Алгоритм.

1. Создаём список соседей, где adj[X] содержит всех соседей узла X.

2. Для подсчёта количества недоступных пар узлов объявляем переменную numberOfPairs. Инициализируем нулём (0).

3. Для хранения количества узлов в текущем компоненте объявляем переменную sizeOfComponent. Инициализируем нулём (0).

4. Для отслеживания количества непросмотренных узлов графа после обхода BFS объявляем переменную remainingNodes. Инициализируем n.

5. Для отслеживания просмотренных узлов объявляем массив visit размером n элементов.

6. Выполняем итерацию по всем узлам, и для каждого узла проверяем, посещен он или нет. Если узел i не посещен, начинаем обход BFS:

• Для обхода дерева используется функция bfs. Для каждого вызова передаются параметрами node, adj и visit. Обход начинается с узла i.

• Мы инициализируем очередь q из целых чисел и помещаем в нее node. Мы также помечаем узел как посещенный и создаем переменную count, чтобы отслеживать количество узлов в этом компоненте. Мы инициализируем count равным 1, чтобы подсчитать узел node.

• Пока очередь не пуста, из очереди извлекается node и выполняются итерации по всем его соседям. Если какой-либо сосед не посещен, мы отмечаем его посещенным, увеличиваем количество посещений на 1 и помещаем его в очередь.

• После того, как очередь становится пустой, мы возвращаем count и сохраняем ешо в sizeOfComponent.

• Количество недостижимых пар узлов с одним узлом в текущем компоненте и другим узлом в любом другом компоненте, кроме текущего компонента и ранее посещенных компонентов, равно sizeOfComponent * (remainingNodes - sizeOfComponent). Это значение добавляется к переменной numberOfPairs.

• Переменная remainingNodes уменьшается на sizeOfComponent, потому что мы добавили все необходимые пары узлов, причем один из узлов находится в текущем компоненте, и мы не хотим добавлять их снова. В результате мы предполагаем, что их больше нет.

7. Возвращаем numberOfPairs

Реализация.

class Solution {
public:
    int bfs(int node, vector<vector<int>>& adj, vector<bool>& visit) {
        queue<int> q;
        q.push(node);
        int count = 1;
        visit[node] = true;

        while (!q.empty()) {
            node = q.front();
            q.pop();
            for (int neighbor : adj[node]) {
                if (!visit[neighbor]) {
                    visit[neighbor] = true;
                    count++;
                    q.push(neighbor);
                }
            }
        }
        return count;
    }

    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        long long numberOfPairs = 0;
        long long sizeOfComponent = 0;
        long long remainingNodes = n;
        vector<bool> visit(n);
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                sizeOfComponent = bfs(i, adj, visit);
                numberOfPairs += sizeOfComponent * (remainingNodes - sizeOfComponent);
                remainingNodes -= sizeOfComponent;
            }
        }
        return numberOfPairs;
    }
};

Анализ сложности.

У нас n – количество узлов, а e – количество рёбер.

• Сложность по времени: O(n+e)

  • Необходимо O(e) времени для инициализации списка соседей и O(n) времени для инициализации массива visit.

  • Каждая операция с очередью в алгоритме BFS занимает O(1) времени, и один узел может быть перемещен только один раз, что приводит к O(n) операций для n узлов. Мы выполняем итерацию по всем соседям каждого узла, который извлекается из очереди, поэтому для неориентированного ребра данное ребро может быть повторено не более двух раз (узлами на обоих концах), что приводит к общему количеству операций O(e) для всех узлов.

  • В результате общее требуемое время составляет O(n+e)

• Сложность по памяти: O(n+e)

  • Построение списка смежности занимает O(e) памяти.

  • Массив visit занимает O(n) памяти.

  • При рекурсивных вызовах функции bfs используется стек, который в наихудшем сценарии необходим для n элементов. В этом случае это заняло бы O(n) памяти.

Способ решения 3. Непересекающееся множество (Union-find).

Интуиция.

Структура данных union-find – это еще один подход к ответам на вопросы, основанный на связности графов. Он может эффективно определять, к какому подключенному компоненту принадлежит узел или ребро, а также размер каждого компонента. Поскольку наша задача состоит в том, чтобы найти размер каждого компонента, который мы затем можем использовать для определения требуемого количества пар узлов, мы также можем использовать структуру данных union-find для решения проблемы.

Структура данных с непересекающимися наборами, также называемая структурой данных поиска объединения или набором поиска слияния, представляет собой структуру данных, в которой хранится коллекция непересекающихся (неперекрывающихся) наборов. Эквивалентно, он хранит разбиение множества на непересекающиеся подмножества. Он предоставляет операции для добавления новых наборов, объединения наборов (замены их объединением) и поиска репрезентативного члена набора. Он реализует две полезные операции:

1. Find – Определение, в какое подмножество входит конкретный элемент. Это может быть использовано для определения того, находятся ли два элемента в одном и том же подмножестве.

2. Union – Объединение двух подмножеств в одно.

Мы перебираем все ребра, производя union двух узлов, соединенных ребром. Это генерирует граф путем вставки всех узлов в компоненты, к которым они принадлежат.

Затем мы перебираем все узлы, чтобы определить, к какому компоненту принадлежит каждый узел, используя операцию find. Мы создаем хэш-карту под названием componentSize, которая сопоставляет узел, который однозначно идентифицирует компонент (операция find возвращает этот узел для всех узлов в компоненте), с размером компонента. Мы увеличиваем размер компонента find(node) на 1 для узла node, поскольку узел принадлежит компоненту find(node). Аналогично, мы покрываем все узлы и получаем размеры всех компонентов в componentSize.

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

Алгоритм.

1. Создается экземпляр класса UnionFind с именем dsu(n).

2. Выполняется итерацию по всем ребрам графа edges и производится операция union для обоих узлов, соединенных ребром.

3. Создается хэш-карта componentSize для сопоставления узла, который уникально идентифицирует компонент, с размером компонента. componentSize[x] возвращает количество узлов в компоненте, к которому относится узел x.

• Выполняем итерацию над всеми узлами, и для каждого узла на единицу увеличиваем componentSize[find(node)].

4. Для подсчёта количества недоступных пар узлов объявляем переменную numberOfPairs. Инициализируем нулём (0).

5. Для отслеживания количества узлов, которые остались после посещения каждого компонента, объявляем переменную remainingNodes. Инициализируем n.

6. Мы проходим по карте componentSize и для каждого элемента в карте выполняем следующее:

• Добавляем к переменной numberOfPairs все узлы, где один узел находится в текущем компоненте, а другие узлы в другом компоненте, за исключением текущего компонента и компонентов, ранее посещённых. Это выполняется так: numberOfPaths += componentSize * (remainingNodes - componentSize).

• Уменьшаем значение remainingNodes на sizeOfComponent, потому что мы добавлили все необходимые пары узлов текущего компонента и не хотим их добавлять снова. Считаем, что их будто бы уже нет.

7. Возвращаем numberOfPairs

Реализация.

class UnionFind {
private:
    vector<int> parent, rank;

public:
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_set(int x, int y) {
        int xset = find(x), yset = find(y);
        if (xset == yset) {
            return;
        } else if (rank[xset] < rank[yset]) {
            parent[xset] = yset;
        } else if (rank[xset] > rank[yset]) {
            parent[yset] = xset;
        } else {
            parent[yset] = xset;
            rank[xset]++;
        }
    }
};

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        UnionFind dsu(n);
        for (auto edge : edges) {
            dsu.union_set(edge[0], edge[1]);
        }
        unordered_map<int, int> componentSize;
        for (int i = 0; i < n; i++) {
            componentSize[dsu.find(i)]++;
        }

        long long numberOfPaths = 0;
        long long remainingNodes = n;
        for (auto component : componentSize) {
            int componentSize = component.second;
            numberOfPaths += componentSize * (remainingNodes - componentSize);
            remainingNodes -= componentSize;
        }
        return numberOfPaths;
    }
};

Анализ сложности.

У нас n – количество узлов, а e – количество рёбер.

• Сложность по времени: O(n+e)

  • Для операций T амортизированная временная сложность алгоритма UnionFind (использующего сжатие пути и объединение по рангу) равна O(alpha(T). Здесь α(T) – обратная функция Аккермана, которая растет настолько медленно, что не превышает 4 для всех разумных T (приблизительно T < 10^600). Поскольку функция растет так медленно, мы считаем, что она равна O(1).

  • Инициализация UnionFind занимает O(n) времени, потому что инициализируются массивы parent и rank, каждый размером n.

  • Выполняются итерации для каждого ребра и операции union для узлов, соединенных ребром, что занимает O(1) времени для операции. Всего, O(e) времени для e рёбер.

  • Затем выполняются итерации для всех узлов и операция find для поиска компонентов. Операция find занимает O(1) амортизационного времени для каждой операции.

  • Выполняются итерации по элементам карты componentSize. У нас не больше n компонентов, потому что всего n узлов. В наихудшем сценарии, определение размера всех компонентов потребует O(n) времени.

  • В результате общее требуемое время составляет O(n+e)

• Сложность по памяти: O(n)

  • Используются массивы parent и rank, которым нужно O(n) памяти каждому.

  • Карте componentSize требуется O(n) памяти в наихудшем случае.