Construct a DAG using Tarjan This is a question related to a homework assignment so I guess I'm asking for hints, if that's ok? Basically, I'm wondering if there is some way to use Tarjan to compress the nodes in every SCC found into one single node, essentially producing a DAG. The problem I'm faced with is that every SCC is obtained as a set but I can't seem to find a way to preserve the edges leading out of the SCC.
Construct a new graph whose vertex set is the strongly connected components. Now go over all edge in the original graph, and if they connect two different strongly connected components, add the corresponding edge to the new graph if it's not already there.