-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$

closed as unclear what you're asking by Juho, David Richerby, vonbrand, Tom van der Zanden, Raphael Feb 19 '16 at 10:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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).
$\endgroup$

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