Как конкурентоспособный программист, человек всегда ищет новые алгоритмы и методы для эффективного решения проблем. Здесь мы собираемся обсудить технику, которая может быть новой для некоторых программистов. Мы также обсудим 3 причины: Что, почему и как?

Так что пристегнитесь, поездка будет гладкой.

Предварительное условие:

Желательно прочитать эту статью, только если вы имеете представление о базовой реализации графа и DFS. Если нет, лучше сначала выучить их, а потом продолжить эту статью.

Что?

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

Время прибытия / время перед посещением / время начала:

Время прибытия узла - это время, когда он впервые обнаруживается в DFS. Это время, когда узел попадает в стек рекурсии.

Время отправления / Время после посещения / Время окончания:

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

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

Почему?

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

Как?

В этом разделе мы обсудим, как реализовать идею.

Интуиция: Основная идея - запустить DFS поверх графа. Мы в основном записываем время прибытия, когда узел посещается впервые. Затем мы начинаем обход неисследованных соседних узлов и аналогичным образом фиксируем время их прибытия. Когда все соседние узлы изучены и он готов к возврату, запишите время его отправления. Эта концепция применяется к каждому узлу графа.

Код:

TIME = 0
dfs (v):
        arrival_time[v] = TIME ++
        visited[v] = true
        for u in adj[v]:
                if visited[u] == false
                        then dfs(u)
   
        departure_time[v] = TIME ++

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

Пример :-

Ключевые моменты:

  1. Время прибытия и отправления всех вершин может варьироваться, так как оно зависит от порядка вставки ребер и начального узла dfs.
  2. Для отключенного графа запустите код dfs для всех неисследованных узлов.
  3. Концепция отметки времени на узле в ядре - это свойство отслеживания с возвратом. Поскольку dfs использует отслеживание с возвратом, мы можем найти его здесь. В то время как в bfs нет концепции возврата, поэтому нет концепции временных меток.

Приложения:

  1. Чтобы проверить, находится ли данный узел в поддереве другого данного узла,
  2. Топологическая сортировка в ориентированном ациклическом графе.
  3. Нахождение мостов графа.
  4. Обнаружение двусвязности в графах.
  5. Нахождение точек сочленения на графике.
  6. Обнаружение цикла в ориентированном графике… и многое другое.

Некоторые проблемы:

  1. Https://www.codechef.com/problems/IITK1P10
  2. Https://www.codechef.com/problems/TAQTREE
  3. Https://www.codechef.com/problems/TYTACTIC
  4. Http://codeforces.com/problemset/problem/383/C

Вот и все! Вы были хорошей аудиторией. Благодарим за терпение.

Предложения по улучшению всегда приветствуются. Не стесняйтесь поделиться этой статьей, если это помогло :)