Изменения

Дан неориентированный [[Основные определения теории графов#Граф| граф ]] <tex> G </tex>. Найти все [[Мост, эквивалентные определения | мосты ]] в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>

Пусть <tex> T </tex> - дерево [[Обход в глубину, цвета вершин | обхода в глубину графа ]] <tex> G</tex>. Ребро <tex> (u, v) </tex> является мостом тогда и только тогда, когда <tex> (u, v) \in T</tex> и из вершины <tex> v</tex> и любого ее потомка нет обратного ребра в вершину <tex> u</tex> или предка <tex> u </tex>