Поиск мостов
Пусть дан связный неориентированный граф. Мост - ребро, при удалении которой граф становится несвязным.
Первым делом введем новые виды ребер :
Ребра самого ДФС (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 -й вершины.
Научимся понимать, какое ребро - ребро ДФС, а какое обратное. Если ребро ведет в уже использованную вершины, то это обратное ребро, иначе ребро ДФС.