Написано: 24.03.2023

1466. Изменить порядок маршрутов, чтобы все пути вели к нулевому городу (Reorder Routes to Make All Paths Lead to the City Zero)

medium

Задание.

Существует n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, так что существует только один способ передвижения между двумя разными городами (эта сеть образует дерево). В прошлом году министерство транспорта решило ориентировать дороги в одном направлении, потому что они слишком узкие.

Дороги представлены соединениями, где connections[i] = [a_i, b_i] представляют дорогу из города a_i в город b_i.

В этом году в столице (город 0) состоится большое событие, и многие люди хотят поехать в этот город.

Ваша задача состоит в том, чтобы переориентировать некоторые дороги таким образом, чтобы каждый город мог посетить город 0.

Верните минимальное количество измененных ребер.

Гарантируется, что после переориентирования до города 0 можно будет добраться из каждого города (решение существует).

Пример 1.

LeetCode-001466a

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

Результат: 3

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

Пример 2.

LeetCode-001466b

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

Результат: 2

Пример 3.

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

Результат: 0

Решение.

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        
    }
};

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

Обзор

Нам дано дерево с n узлами, где каждый узел представляет собой город, пронумерованный от 0 до n - 1. Ребра называются дорогами между городами.

Дерево, приведенное в задаче, имеет направленные ребра, обеспеченные соединениями (connections).

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

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

LeetCode-001466c

1. Дочерний узел – Узел, который находится на одно ребро дальше от данного узла в корневом дереве. На приведенном выше изображении узлы 3, 4 являются дочерними по отношению к 1, который называется родительским. (Когда мы рассматриваем 0 как корень).

2. Потомки – Потомками узла являются дочерние элементы, дочерние элементы дочерних элементов и так далее. На приведенном выше изображении все узлы 3, 4, 6, 7, 9 являются потомками 1.

3. Поддерево – Поддерево узла T – это дерево S, состоящее из узла T и всех его потомков в T. Поддерево, соответствующее корневому узлу, является всем деревом.

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

Интуиция

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

Рассмотрим на примере.

LeetCode-001466d

Поэтому наша задача сводится к тому, чтобы подсчитать количество ребер в дереве с корнем в узле ‘0’, которые направлены от родительского узла к дочернему узлу.

Мы должны пройти по всему дереву, чтобы определить количество таких ребер, которые направлены от родительского узла к дочернему. Чтобы обойти дерево, мы можем использовать алгоритм обхода графа, такой как поиск в глубину (DFS).

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

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

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

Чтобы обойти все дерево, нужно найти способ добраться от узла 0 ко всем узлам в любом случае. Это возможно, если обрабатывать ребра как ненаправленные. Мы добавляем противоположное ребро от узла b к узлу a для каждого заданного ребра в connections от узла a к узлу b. Давайте назовем добавленное нами ребро “искусственным” ребром, а ребро, присутствующее в connections, – “оригинальным” ребром.

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

Если мы используем “оригинальное” ребро для перемещения от родительского узла к дочернему узлу, это означает, что нам нужно перевернуть это ребро. Всякий раз, когда мы сталкиваемся с таким ребром, мы увеличиваем нашу переменную ответа на 1.

Различать “исходные” и “искусственные” ребра можно многими различными способами (присваивая логические значения, определенные числа и т.д.). В этой статье мы свяжем дополнительное значение с каждым ребром – 1 для “оригинальных” ребер и 0 для “искусственных” ребер.

Мы также устанавливаем переменную ответа count = 0, чтобы подсчитать количество ребер, которые должны быть перевернуты. Теперь мы запускаем DFS с узла 0 и продвигаемся вниз по дереву (от родительского к дочернему). Если во время обхода мы натыкаемся на “исходное” ребро, то есть ребро, помеченное знаком 1, мы увеличиваем count на единицу. Мы не изменяем count, если сталкиваемся с “искусственным” ребром. Мы можем объединить эти две операции и выполнить count += sign, где sign равен либо 0, либо 1, указывая на “искусственное” или “оригинальное” ребро.

При завершении обхода наш ответ содержится в переменной count.

Алгоритм

1. Создадим переменную count для подсчета ребер, которые нужно перевернуть. Инициализируем ее через 0.

2. Создадим список соседей adj, который содержит список пар целых чисел, таких, что adj[node] содержит всех соседей узла в форме (neighbor, sign), где neighbor – это номер узел-соседа, а sign обозначает направление ребра, т.е. является ли оно “исходным” или “искусственным”.

3. Запускаем обход DFS.

Мы используем функцию dfs для выполнения обхода. Для каждого вызова передаются node, parent, adj в качестве параметров. Мы начинаем с узла 0 и родительского элемента как -1.
Выполняем итерацию по всем дочерним элементам node (узлам, которые имеют общее ребро), используя adj[node]. Для каждого child, sign проверяем в adj[node], равны ли child и parent. Если равны, то child больше не посещается.
Если child не равен parent, выполняется count += sign и рекурсивно вызывается dfs с node = child и parent = node. В конце обхода dfs у нас в count есть общее количество ребер, которые необходимо перевернуть.

4. Возвращаем count.

Реализация

class Solution {
public:
    int count = 0;
    void dfs(int node, int parent, vector<vector<pair<int, int>>>& adj) {
        for (auto& [child, sign] : adj[node]) {
            if (child != parent) {
                count += sign;
                dfs(child, node, adj);
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& connection : connections) {
            adj[connection[0]].push_back({connection[1], 1});
            adj[connection[1]].push_back({connection[0], 0});
        }
        dfs(0, -1, adj);
        return count;
    }
};

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

Здесь n – это количество узлов.

Сложность по времени O(n)
- Нужно O(n) времени для инициализации списка соседей.
- Функция dfs посещает каждый узел один раз, что занимает в общей сложности O(n) времени. Поскольку у нас есть неориентированные ребра, каждое ребро может быть повторено только дважды (по узлам в конце), что приводит к общему количеству операций O(e) при посещении всех узлов, где e – количество ребер. Поскольку данный граф является деревом, существует n−1 неориентированных ребер, поэтому O (n + e) = O(n).
Сложность по памяти O(n)
- Для создания списка соседей необходимо O(n) памяти.
- Для рекурсивных вызовов dfs необходим стек, размером O(n) (в наихудшем варианте).

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

Интуиция

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

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

Алгоритм

1. Создадим переменную count для подсчета ребер, которые нужно перевернуть. Инициализируем ее через 0.

3. Запускаем обход BFS.

Мы используем функцию dfs для выполнения обхода. Для каждого вызова передаются node, n, adj в качестве параметров. Мы начинаем с узла 0.
Создаётся массив visit размером n для отслеживания посещённых узлов.
Инициализируется очередь q из целых чисел и первоначально в неё помещаетя 0 (корневой узел). Также 0 отмечается, как посещенный.
Пока очередь не пуста, из неё извлекается node и выполняеется итерация по всем его соседям, используя adj[node]. Для каждого neighbor, sign из adj[node], проверяется, посещался ли neighbor. Если нет, neighbor отмечается посещенным, выполняется count += sign и neighbor помещается в очередь.

4. Возвращаем count.

Реализация

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

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

    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& connection : connections) {
            adj[connection[0]].push_back({connection[1], 1});
            adj[connection[1]].push_back({connection[0], 0});
        }
        bfs(0, n, adj);
        return count;
    }
};

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

Здесь n – это количество узлов.

Сложность по времени: O(n)
- Нужно O(n) времени для инициализации списка соседей и O(n) для инициализации массива visit.
- В алгоритме BFS каждая операция помещения в очередь O(1) времени, и один узел может быть перемещен только один раз, что приводит к O(n) операций для n узлов. Мы выполняем итерацию по всем соседям каждого узла, который извлекается из очереди, поэтому для неориентированного ребра данное ребро может быть повторено не более двух раз (узлами на обоих концах), что приводит к общему количеству операций O(e) для всех узлов. Как упоминалось в предыдущем подходе, O(e) = O(n), поскольку граф представляет собой дерево.
Сложность по памяти: O(n)
- Для создания списка соседей необходимо O(n) памяти.
- Для массива visit необходимо O(n) памяти.
- Для очереди необходимо O(n) памяти (в наихудшем варианте).