Collapse vertices after Tarjan found the strongly connected component

Question

Suppose there are many vertices with some value in a circled graph.

After using Tarjan to find out these SCCs, I want to turn each whole SCC into two vertices(not one), one with the highest value among those vertices in this SCC and another with the lowest value.

Let those vertices which are connected to this SCC to point to the vertex with lowest value, and let vertices which are pointed at from the SCC to be pointed at from the vertex with highest value.

That is, like 1(4) -> 2(3) <-> 3(5) -> 5(1) <-> 4(6) -> 1(4), weights in the parentheses, which is a circle. I want to translate it into something like 1(4) -> 2(3) -> 3(5) -> 4(1) -> 5(6) , 1(4) -> 4(1)

But I cannot figure out how to implement this, Please help.

I'm using C and adjacency list to store the graph.

Sorry for poor English, I hope it's clear enough to be understood.

Answer 1

the following ideas should get you started:

• denote the original graph with G, the scc set with S, and a new graph of interconnected sccs with SG.
• you need the mappings of vertices to scc scc: V(G) -> S, and of sccs to min and max valued vertices min/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) in E(G) creating an edge (max(scc(u)),min(scc(v))) in E(SG) for each of them unless it already exists.
• for each scc s in S add (min(S), max(S)) to E(SG).

you probably need to think about how to resolve ties among max-/min-valuesd nodes in a scc.