Вопрос:

ссылка: https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/

Дан направленный ациклический граф с n вершинами, пронумерованными от 0 до n-1, и массив edges, где edges[i] = [fromi, toi] представляет собой направленное ребро от узла fromi до узла toi.

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

Обратите внимание, что вы можете возвращать вершины в любом порядке.

Пример 1:

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Пример 2:

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]
Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

Ограничения:

  • 2 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi < n
  • Все пары (fromi, toi) различны.

Решение:

Подход: этот код является решением проблемы, в которой нам дан ориентированный граф с вершинами, помеченными от 0 до n-1, и список ребер, представленный парами целых чисел. Цель состоит в том, чтобы найти наименьшее множество вершин, из которого мы можем добраться до всех остальных вершин графа.

Код начинается с инициализации массива indegree размера n, в котором будет храниться степень вхождения каждой вершины. Степень вхождения вершины представляет собой количество входящих ребер в эту вершину.

Затем он перебирает список ребер, используя цикл for-each. Для каждого ребра увеличивается степень вхождения второй вершины (edge.get(1)) на единицу. Этот шаг позволяет нам подсчитать количество входящих ребер для каждой вершины в графе.

После подсчета степени вхождения каждой вершины код инициализирует пустой список с именем ans, в котором будут храниться вершины с нулевой степенью вхождения. Затем он перебирает все вершины от 0 до n-1, используя цикл for. Если степень вхождения текущей вершины i равна нулю, это означает, что в эту вершину нет входящих ребер. В этом случае вершина добавляется в список ans.

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

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        int[] indegree = new int[n];
        for (List<Integer> edge : edges) {
            indegree[edge.get(1)]++;
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                ans.add(i);
            }
        }

        return ans;
    }
}

Временная сложность: O(E + V), где E — количество ребер, а V — количество вершин в графе.

Пространственная сложность:O(V)

Заключение:

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

Удачного кодирования.