Graph Theory37 sections · 1633 units
Open in Course

Pattern: SCC Applications

When to use strongly connected components.

Use SCCs when:

  • You need to find cycles in directed graphs
  • You want to condense a graph into a DAG
  • Nodes in the same cycle should be treated equivalently

After SCC condensation:

  • The condensed graph is a DAG
  • You can apply topological sort
  • DP on the DAG often follows

Example: In a road network, cities in the same SCC are all mutually reachable. Condense to DAG, then find reachable components.