1
$\begingroup$

I understand that when you know the strongly connected componentes of a directed graph, it can help us detect the cycles of the graph, as all the cycles will occur in each SCC. But how can just knowing how many SCC there are help us finding the cycles? I don't quite understand, all input appreciated.

$\endgroup$
1
$\begingroup$

I figured out the answer, in case anyone is interested. If the number of SCC equals the number of nodes, then the graph must be acyclic since any cycle would be a part of two SCC, which is clearly impossible. The converse is also true; if the number of SCC is less than the number of nodes, then there must be at least one SCC with more than one node per the pigeonhole principle and therefore this SCC, and hence the entire graph, must have a cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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