Показать сообщение отдельно
  #2  
Старый 11.08.2013, 12:17
Новичок

Отправить личное сообщение для haddx Посмотреть профиль Найти все сообщения от haddx
 
Регистрация: 10.08.2013
Сообщений: 2

В общем остановился на реализации через преобразование графа в остовное дерево (из любой точки) и удаление в цикле всех точек дерева, которые имеют только одну смежную и не являются частями мостов (они просто висят в воздухе и нам не нужны), таким образом мы получаем даже из самых страшных графов сильно сжатое дерево, состоящее преимущественно из мостов, и пути с наибольшим числом этих самых мостов находятся легко через dfs или bfs.