Having a graph and all of it's strongly connected components, I was wondering what the most efficient way to find arcs that connect two SCC. All the solutions I found involve running through all the nodes, and I was wondering if there was a way to do it without having done that, in particular, during the Tarjan algorithm I used to find SCC's in the graph. ANyway to do it in a linear fashion?

Thank you very much!

  • $\begingroup$ Scanning through all the nodes does take only linear time. Perhaps I'm not understanding what you are asking. $\endgroup$ – D.W. Mar 19 '18 at 0:10
  • $\begingroup$ yes but I was wondering if there was a way of doing it during Tarjan's algorithm when we are finding the SCC's $\endgroup$ – Miguel Barros Mar 19 '18 at 10:29
  • 1
    $\begingroup$ What would prevent you from doing that during Tarjan's algorithm? I don't understand the nature of your confusion. $\endgroup$ – D.W. Mar 19 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.