Алгоритм линейного времени, чтобы сделать граф сильно связным

Question

У нас есть слабоациклический орграф.

Также нам дано множество A, которое содержит вершины G с нулем в степени и множество B, которое содержит вершины с нулем вне степени.(размер A меньше размера B).

Кроме того, мы также знаем, что если элементы в A и B имеют определенный порядок (например, A = a1, a2, ..., amи B = b1, b2, ..., bn) DFS, запущенная при ai, посещает bi (1≤ i ≤ m).

Можно ли разработать линейный алгоритм времени, который делает G прочно связанным, добавляяк нему как можно меньше ребер?

Answer 1

Добавить дуги b _j -> a _{j + 1} для j = 1, ..., m-1 и дуг b _j -> a ₁ для j = m, ..., n.

Полученный граф сильно связан, потому что a и b сильно связаны добавленными дугами и путями от a _i до b _i , и для каждого узла x существует существуют i, j такие, что в исходном графе существует путь от _i до x и путь в исходном графе от x до b _j .

Мы не можем использовать меньше дуг, потому что исходящая дуга должна быть добавлена ​​к каждому из b ₁ , ..., b _n .

Answer 2

Отредактировано - следующее не дает решения с наименьшим количеством ссылок:

Вы можете запустить http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm в линейном времени.Я предлагаю вам сделать это и отметить, что «ни один из сильно связанных компонентов не будет идентифицирован ни перед кем из его преемников».Поэтому первый сильно компонент из графа не должен быть преемником любого из других компонентов.Я предлагаю каждый раз, когда вы создаете сильно связанный компонент, который не имеет преемника, вы добавляете ссылку, соединяющую его с этим первым компонентом.Я предлагаю вам также добавлять ссылку каждый раз, когда вы по существу перезапускаете алгоритм Тарьяна с помощью нерекурсивного вызова strongconnect (), соединяющего первый компонент с вершиной, с которой вы перезапускаете.

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