Учитывая ориентированный граф, удалите ребро между двумя узлами, если между ними есть альтернативный путь.Пример: дано a-> b, b-> c, a-> c, удалить a-> c.Существует ли эффективный алгоритм для подсчета количества удаленных ребер?
Из вики Сильно связанный компонент :
Ориентированный граф является ациклическим тогда и только тогда, когда он не имеет сильно связанных подграфов с более чем одной вершиной, поскольку ориентированный циклсильно связанный, и каждый нетривиальный сильно связанный компонент содержит по крайней мере один направленный цикл.
Вы можете использовать Алгоритм сильносвязанных компонентов Тарьяна , чтобы найти SCC.А затем удалите одно ребро из каждого компонента.
Затем вам нужно будет повторить весь процесс, так как каждый нетривиальный сильно связанный компонент содержит хотя бы один направленный цикл.
В общем случаечисло циклов NP-трудно, как если бы вы могли считать все циклы за полиномиальное время, то вы также можете обнаружить существование гамильтонова цикла.Но Гамильтонов путь NP-труден.