First of all I did find similar questions here on Computer Science but nothing what would provide real answer for this problem.
I have a graph which i condense into SSC (strongly connected components) by Kosaraju's algorithm. Now what I need is to find connections between those SSCs. The best would be to somehow inject this process into Kosaraju's runtime but I did not come up with tangible solution there. My algorithm is logically similar to the one on wikipedia: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm (I can't provide my code because it is a school assignment)
I would very much appreciate any tip from smarter folk than me. :D
More information/What I came up with: I thought about it and did not come up with better solution then after finishing Kosaraju I will go through each vertex, check his in/out edges and if the edge's other side is not part of this SSC than add this edge as connecting edge to my SSC. But this process is very expensive as i need to:
- For each vertex go over its all edges
- Compare every edge end with vertexes in SSC.
Computation would be something like edges X [vertexes in its SSC]. If my graph would be one huge SSC than I would basically get V*E. There is no way this is best approach, I bet it is actually one of the worst.