HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Construct a DAG using Tarjan

Submitted by: @import:stackexchange-cs··
0
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.