patternMinor
Construct a DAG using Tarjan
Viewed 0 times
constructtarjandagusing
Problem
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.
Solution
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.
Context
StackExchange Computer Science Q#71963, answer score: 2
Revisions (0)
No revisions yet.