-3
$\begingroup$

After finding the Strongly Connected Components of a graph and putting each SCC in a list, how i can contract each list of nodes into one node?

Thanks!

$\endgroup$
  • 2
    $\begingroup$ This seems to be a programming question, which is offtopic here. Or is there a conceptual question you're having? (Community votes, please!) $\endgroup$ – Raphael Feb 17 '16 at 11:24
  • 2
    $\begingroup$ In any case, what have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Feb 17 '16 at 11:25
1
$\begingroup$

I am going to assume that you want to build the graph of strongly connected components.

Traverse the edges of the graph once more. For every edge (x,y):

  • If x and y belong to the same SCC you do nothing.
  • Else insert edge (SCC[x],SCC[y]) in a new graph (the graph of strongly connected components).
| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.