algorithm - Collapse vertices after Tarjan found the strongly connected component -

suppose there many vertices value in circled graph.

after using tarjan find out these sccs, want turn each whole scc two vertices(not one), 1 highest value among vertices in scc , lowest value.

let vertices connected scc point vertex lowest value, , let vertices pointed @ scc pointed @ vertex highest value.

that is, 1(4) -> 2(3) <-> 3(5) -> 5(1) <-> 4(6) -> 1(4), weights in parentheses, circle. want translate 1(4) -> 2(3) -> 3(5) -> 4(1) -> 5(6) , 1(4) -> 4(1)

but cannot figure out how implement this, please help.

i'm using c , adjacency list store graph.

sorry poor english, hope it's clear enough understood.

the following ideas should started:

• denote original graph g, scc set s, , new graph of interconnected sccs sg.
• you need mappings of vertices scc scc: v(g) -> s, , of sccs min , max valued vertices min/max: s -> v(g), can built during tarjan scc construction.
• set vertices of sg image of min/max.
• afterwards you'll build sg iterating on edges (u,v) in e(g) creating edge (max(scc(u)),min(scc(v))) in e(sg) each of them unless exists.
• for each scc s in s add (min(s), max(s)) e(sg).

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