Это пятый день моего участия в августовском испытании обновлений, подробности о мероприятии:Испытание августовского обновления

leetcode-802 - Найти конечное безопасное состояние

[ссылка на блог]

Путь обучения Цая🐔

Наггетс Главная

[Название Описание]

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

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

В качестве ответа возвращает массив всех безопасных начальных узлов графа. Элементы в массиве ответов должны бытьпо возрастаниюрасположение.

Ориентированный граф имеетnузлы, нажмите0прибытьn - 1число, гдеnДа graphколичество узлов. График дается в следующем виде:graph[i]это числоjсписок узлов, удовлетворяющих(i, j)является направленным ребром графа.

Пример 1:

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。

Пример 2:

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]

намекать:

n == graph.length
1 <= n <= 10⁴
0 <= graph[i].length <= n
graph[i]Расположены в строго возрастающем порядке.
Граф может содержать петли.
Количество ребер в графе находится в диапазоне[1, 4 * 10⁴]Внутри.

[Название ссылки]

ссылка на тему литкода

[адрес гитхаба]

ссылка на код

[Введение в идеи]

Идея первая:дфс+насилие

dfsпройти все узлы
Каждый раз, когда узлы dfs не будут пересекать один и тот же узел, раз они одинаковы, это небезопасно (текущая проверка безопасности немного сложна, и я хочу оптимизировать идею)
в состоянии пройтиhashсделать
TLEохватывать

Set<Integer> set = new HashSet<>();
 public List<Integer> eventualSafeNodes(int[][] graph) {
     int[] arr = new int[graph.length];
     for (int i = 0; i < graph.length; i++) {
         set = new HashSet<>();
         set.add(i);
         arr[i] = dfs(graph, i,set) ? 1 : 0;
     }
     List<Integer> res = new ArrayList<>();
     for (int i = 0 ; i < arr.length;i++){
         if (arr[i]>0){
             res.add(i);
         }
     }
     return res;
 }

 public boolean dfs(int[][] graph, int i,Set<Integer> set) {
     if (i>= graph.length){
         return false;
     }
     for (int tar: graph[i]
          ) {
         if (set.contains(tar)){
             return false;
         }
         Set<Integer> temp = new HashSet<>();
         temp.addAll(set);
         temp.add(tar);
         boolean flag = dfs(graph,tar,temp);
         if (!flag){
             return false;
         }
     }
     return true;
 }

$Временная сложность O (n ^ {2})$

Идея 2: Идея оптимизации 1

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

Set<Integer> security = new HashSet<>();
        public List<Integer> eventualSafeNodes(int[][] graph) {
            int[] arr = new int[graph.length];
            for (int i = 0; i < graph.length; i++) {
                Set<Integer> set = new HashSet<>();
                set.add(i);
                arr[i] = dfs(graph, i, set) ? 1 : 0;
            }
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > 0) {
                    res.add(i);
                }
            }
            return res;
        }

        public boolean dfs(int[][] graph, int i, Set<Integer> set) {
            if (i >= graph.length) {
                return false;
            }
            for (int tar : graph[i]
            ) {
                if (security.contains(tar)) {
                    continue;
                }
                if (set.contains(tar)) {
                    return false;
                }
                Set<Integer> temp = new HashSet<>();
                temp.addAll(set);
                temp.add(tar);
                boolean flag = dfs(graph, tar, temp);
                if (!flag) {
                    return false;
                } else {
                    security.add(tar);
                }
            }
            return true;
        }

$Временная сложность O (n ^ {2})$

Идея третья:Направленный граф + обратный граф + BFS + топологическая сортировка

Добавлены интересные новые знания
Этот вопрос в основном относится кРешение проблемы трехлистного боссапонятный перевод (Сяо Бай такой сложный
Это первое введение в серию ежедневных вопросов.топологическая сортировкаКонцепция чего-либо
Во-первых, давайте поговорим о связи между этой темой и топологической сортировкой.
Этот вопрос можно анализировать в соответствии со значением вопроса, а последовательность искомых результатов относится к
- Все узлы в последовательности гарантированно находятся в пределах направленного пути.Ациклический
Одно из свойств топологической сортировки тоже очень простое:
Если есть два узла (u, v) с направленным путем u->v, то v не должен иметь направленного пути к u (ациклический)
в состоянии получитьтопологический порядок ориентированного ациклического графаПредпосылка:
- Мы должны иметь возможность найти (по крайней мере) одну «точку с нулевой степенью входа» и поставить ее в очередь в начале.
Природа как раз соответствует смыслу названия
Затем объясните два определения.
- В-степень: Все в состоянииприбытьКоличество ребер этого узла
- Степень выхода: все из этого узлаОтправлятьсяколичество сторон
Этот вопрос теперь может установить все градусы на 0Нет никакого способа добраться до этого узлаузлы в результирующий набор
Помещение этих узлов в голову топологического сорта не влияет на определение топологической последовательности.
Для текущего извлеченного узлаx, пересекаяxвсе степени
пройти всеузел y указывает непосредственно на x
сделать с тобойминус одиндействовать
- Поскольку узел x был извлечен из очереди, ондобавить в топологический порядоксередина
- эквивалентно удалению узла x из ориентированного графа
- Соответствующее ребро из x также должно быть удалено
- Эффект заключается в том, что узел y подключен к xминус один
сделай это на yминус одинПозже
- Проверьте, равна ли степень y 0
- Если 0, поставить в очередь y
- когда степень вхождения y равна 0
- Объясните, что существует ориентированный граф.Все узлы до y добавляются в топологический порядоксередина
- В этом случае y можно использовать какзаголовок фрагмента топологического порядкаДобавлен
- не нарушая определения топологического порядка
В этом вопросе, если вы хотите определить, безопасно ли определенное количество узлов x
Недостаточно поставить в очередь x в начале и запустить топологическую сортировку.
- потому что вход неМожет подтвердить, равна ли степень входа узла 0, то есть узел не может быть непосредственно добавлен в топологическую последовательность
Это предложение можно также интерпретировать как, когдаСтепень неопределенности узла x равна 0когда
Степень входа узла y не может быть уменьшена до 0 в соответствии с описанной выше операцией.
Следовательно, в соответствии с предыдущим процессом доказательства можно построить перевернутый граф после перестановки всех ребер.
- Если степень входа равна 0, она соответствует точке, степень выхода которой равна 0 в исходном изображении.
- Степень выхода исходного изображения равна 0, что означает, что точка изменена на безопасный узел.
- И все ребра, указывающие на этот узел, также могут представлять безопасность.
Таким образом, весь процесс состоит в том, чтобы перевернуть график
запустить топологическую сортировку
Если узел появляется в топологической последовательности
объяснить еговстал в очередь
объяснить егоСтепень входа равна 0 (соответствует исходной степени исходного изображения 0)
это безопасно
Остальные узлы являются незащищенными узлами в кольце.
Связанное сопоставление(Подробности см. в пояснении публичного аккаунта предыдущего трехлистного босса)
Чтобы все могли лучше понять, почему решение может быть решено в зависимости от степени входа и выхода (топологической сортировки) графа, рисунок выглядит следующим образом.
Инициализировать карту на основе входного массива

обратное отображение

Очередь с приоритетным входом со степенью входа 0

После того, как 5 исключен из очереди, все узлы, достигнутые 5, имеют входную степень -1.

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

6 из

2 из

4 из

Конечная очередь пуста, и в обратном графе нет узлов со степенью входа 0 (в прямом графе нет узлов со степенью исхода 0).

Отсканированные защищенные элементы сортируются по размеру в результирующем наборе.

int N = (int)1e4+10, M = 4 * N, idx = 0;
int[] e = new int[M], he = new int[N], ne = new int[M];
int[] cnts = new int[N];
void add(int a, int b){
    e[idx] = b;
    ne[idx] = he[a];
    he[a] = idx;
    idx++;
}
public List<Integer> eventualSafeNodes(int[][] graph) {
    //初始化图
    Arrays.fill(he,-1);
    int n = graph.length;
    //构造反向图
    for (int i = 0; i < n; i++) {
        for (int num: graph[i]
             ) {
            //反向构建
            add(num,i);
            //统计反向图的入度（原图的出度）
            cnts[i]++;
        }
    }
    //BFS求拓扑排序
    Deque<Integer> dq = new ArrayDeque<>();
    //将所有反向图入度为0的节点加入拓扑序列
    for (int i = 0 ; i < cnts.length; i++){
        //入度为0的加入bfs队列
        if (cnts[i] == 0)dq.add(i);
    }
    while (!dq.isEmpty()){
        int temp = dq.poll();
        for (int i = he[temp]; i !=-1 ; i = ne[i]) {
            int j= e[i];
            //减掉当前入度后为0的可以继续加入bfs队列
            if (--cnts[j]==0)dq.addLast(j);
        }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (cnts[i] == 0) ans.add(i);
    }
    return ans;
}

Временная сложность: O(n + m)