Поиск мостов

Пусть дан связный неориентированный граф. Мост - ребро, при удалении которой граф становится несвязным.

Первым делом введем новые виды ребер :

Ребра самого ДФС (tree edge или ребро дерева).

Ребра не посещенные в ДФС (back edge или. обратное ребро).

Пусть есть ребро u → v , в каком случае оно является мостом, понятно, что обратное ребро не может быть мостом, потому что мы уже посещали обе вершины и следовательно есть путь по ребрам самого ДФС. Теперь разберемся с ребрами ДФС. Они являются мостом, только если нет пути по обратным ребрам в какого-то из предков v . Так как иначе мы можем удалить это ребро, но при этом останется путь по обратным ребрам.

Давайте докажем, что если путь до предка существует, то существует и путь, такой, что нам достаточно пройти по одному обратному ребру. Пусть такого пути не существует, но при этом есть какой-то путь из n обратных ребер, тогда давайте посмотрим куда могут вести эти ребра, они могут вести либо в поддерево вершины u , либо в нее саму, либо в наддерево, в случае поддерева или самой вершины мы можем их убрать, так как есть путь по ребрам ДФС, в случае наддерева же нам достаточно сохранить только одно ребро в наддерево.

Тогда давайте введем d p i

- минимальный 

t i n

такой вершины, до которой мы можем добраться за какое-то количество ребер ДФС и одно обратное. Как его пересчитывать. Очень просто : у нас есть три возможных значения динамики.

d p i = m i n ( t i n i , d p i )

d p i = m i n ( d p i , d p s o n ) , где s o n

- сын 

i -й вершины

d p i = m i n ( d p i , t i n b a c k ) , где b a c k

- вершина, для которой есть обратное ребро из 

i -й вершины.

Научимся понимать, какое ребро - ребро ДФС, а какое обратное. Если ребро ведет в уже использованную вершины, то это обратное ребро, иначе ребро ДФС.