Как конкурентоспособный программист, человек всегда ищет новые алгоритмы и методы для эффективного решения проблем. Здесь мы собираемся обсудить технику, которая может быть новой для некоторых программистов. Мы также обсудим 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 - количество ребер в графе.
Пример :-
Ключевые моменты:
- Время прибытия и отправления всех вершин может варьироваться, так как оно зависит от порядка вставки ребер и начального узла dfs.
- Для отключенного графа запустите код dfs для всех неисследованных узлов.
- Концепция отметки времени на узле в ядре - это свойство отслеживания с возвратом. Поскольку dfs использует отслеживание с возвратом, мы можем найти его здесь. В то время как в bfs нет концепции возврата, поэтому нет концепции временных меток.
Приложения:
- Чтобы проверить, находится ли данный узел в поддереве другого данного узла,
- Топологическая сортировка в ориентированном ациклическом графе.
- Нахождение мостов графа.
- Обнаружение двусвязности в графах.
- Нахождение точек сочленения на графике.
- Обнаружение цикла в ориентированном графике… и многое другое.
Некоторые проблемы:
- Https://www.codechef.com/problems/IITK1P10
- Https://www.codechef.com/problems/TAQTREE
- Https://www.codechef.com/problems/TYTACTIC
- Http://codeforces.com/problemset/problem/383/C
Вот и все! Вы были хорошей аудиторией. Благодарим за терпение.
Предложения по улучшению всегда приветствуются. Не стесняйтесь поделиться этой статьей, если это помогло :)