148
правок
Изменения
Нет описания правки
==Постановка задачиДвупроходный алгоритм==Дан неориентированный граф. Требуется определить его Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]]. Задачу будем решать неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]].
'''Первый проход
Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти точки сочленения.]] <br>
Определим для каждой вершины две величины: <tex> enter [i] </tex> - время входа поиска в глубину в вершину <tex> i </tex>, <tex> return [i] </tex> – минимальное из времен входа вершин, достижимых из <tex> i </tex> по дереву <tex> dfs </tex> и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром. <br>
'''Псевдокод первого прохода:
enter[v] = return[v] = time++;
used[v] = true;
