Изменения

Перейти к: навигация, поиск

Построение компонент вершинной двусвязности

2 байта убрано, 08:48, 11 декабря 2011
Двупроходный алгоритм
'''Второй проход
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : return[u] \ge enter[v] </tex>. <br> Это так же также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
Анонимный участник

Навигация