the following ideas should get you started:
- denote the original graph with
G
, the scc set withS
, and a new graph of interconnected sccs withSG
. - you need the mappings of vertices to scc
scc: V(G) -> S
, and of sccs to min and max valued verticesmin/max: S -> V(G)
, which can be built during the tarjan scc construction. - set the vertices of
SG
to the image of min/max. - afterwards you'll build
SG
by iterating over all edges(u,v)
inE(G)
creating an edge(max(scc(u)),min(scc(v)))
inE(SG)
for each of them unless it already exists. - for each scc
s
inS
add(min(S), max(S))
toE(SG)
.
you probably need to think about how to resolve ties among max-/min-valuesd nodes in a scc.