Graph Theory37 sections · 1633 units
Open in Course

Recognizing SCC

Bidirectional reachability ...

The problem asks if you can go from any city to any other city. That is asking if the graph is strongly connected.

If the graph has exactly 11 SCC (all nodes in the same component), answer is YES. If there are 22 or more SCCs, answer is NO.

To find a counterexample, pick two nodes from different SCCs. Look for a source SCC (in-degree 00 in the condensation) and a sink SCC (out-degree 00). A node in the source cannot be reached from a node in the sink.