Нахождение дуг между сильно связанными компонентами

Question

Имея график и все его сильно связанные компоненты, мне было интересно, какой самый эффективный способ найти дуги, соединяющие два SCC. Все решения, которые я нашел, включают в себя прохождение всех узлов, и мне было интересно, есть ли способ сделать это, не делая этого, в частности, во время алгоритма Тарьяна, который я использовал для поиска SCC на графике. В любом случае, делать это линейно?

Большое спасибо!

Answer 1

Просто сделайте связи между различными вершинами указателем и измените значение каждой вершины данного SCC на одно и то же значение.

Таким образом, вам не нужно ничего "искать".

Ex: 1->2->3->4->1

Таким образом, вы получите SCC, который содержит 1234

then 4->5
and 5->6->7->5

Если вы храните соединения в виде указателей, вам просто нужно изменить значение 5 в вершины 5 на 6, а затем перейти к указателю от 4 до 5, чтобы получить 6. Я не очень ясно надеюсь, что вы поняли идею.