Skip to main content
📜 WAYPOINT LESSON

Recognizing SCC Problems

⭐⭐⭐ advanced⏳ 35 min read📍 Lesson 151 of 281

Mutual reachability, propagating swaps, 'same group' sizes, and digraph DP that back edges break — the four signatures of SCC.

The four signatures

  1. "u reaches v AND v reaches u" — mutual reachability IS the SCC relation.
  2. Bidirectional swaps that propagate: swap(i,j) and swap(j,k) allowed → one component {i, j, k}.
  3. "Group" answers — SCC sizes.
  4. DP on a digraph where back edges break the state — condense first.

Anti-signature: a DAG needs no SCC pass; undirected connectivity is not SCC territory.

⚡ Now practice

Ready to Code
SCC TrioCount and size components, count distinct condensation edges, and label components — with an undirected misread, a dedupe miss, and an O(n·m) near-miss.
3 challenges · · ~110 min