SCC (Edge Flip Trick)

A Strongly Connected Component (SCC) of vertex v is the largest set of vertices S containing v, such that for every pair of vertices a, b in S there exists a path from a to b AND from b to a.

In other words: in an SCC, everyone can reach everyone.

Key observation — the "hub" trick: If we pick one vertex as a "hub" (e.g., our house), we only need to check:

• Who can the hub reach? (forward DFS)
• Who can reach the hub? (DFS on reversed graph)

The intersection of these two sets gives us the hub's SCC! Why? Because if Bartek can reach our house, and from our house we can reach Dominik, then Bartek can reach Dominik — through our house.

Example: Graph with 5 vertices:

• 0→1, 1→2, 2→0, 2→3, 3→4
• From vertex 0 we can reach: {0, 1, 2, 3, 4}
• Who can reach 0 (DFS on reversed): {0, 1, 2}
• SCC(0) = {0, 1, 2} ∩ {0, 1, 2, 3, 4} = {0, 1, 2}
• Vertices 3 and 4 are NOT in SCC(0), because they can't reach 0.

Instead of asking each candidate separately "Can you reach me?", we use a clever trick:

Reverse ALL edges in the graph — every arrow changes to the opposite direction.

Why does this help? Because if someone can reach us via path: Bartek → Kasia → Our House

Then after reversing edges, that path becomes: Our House → Kasia → Bartek

Now we can walk that path with DFS from our house! One DFS on the reversed graph replaces many separate DFS searches.

Formally:

• If a path A → B exists in the original graph, then after reversing a path B → A exists
• If NO path A → B exists, then after reversing NO path B → A exists

This means the set of vertices reachable from our house on the reversed graph is EXACTLY the same set as vertices that can reach us on the original graph!

Input: Directed graph and a starting vertex (our house).

Step 1: Reverse edges Create a reversed graph — for each edge u→v add v→u.

Step 2: Forward DFS Run DFS from our house on the original graph. Save the set who_i_can_reach.

Step 3: DFS on reversed graph Run DFS from our house on the reversed graph. Save the set who_can_reach_me.

Step 4: Intersection SCC = who_i_can_reach ∩ who_can_reach_me

Example on graph {0:[1], 1:[2], 2:[0,3], 3:[4], 4:[]}:

Complexity: O(V+E) — two DFS searches + one edge reversal!

We need to prove two things:

Part 1: If someone CAN reach us → DFS on reversed graph WILL find them

Proof: Let there be a path v₁ → v₂ → ... → vₖ → our_house on the original graph. After reversing edges, this path becomes our_house → vₖ → ... → v₂ → v₁. DFS from our house on the reversed graph can walk this path and find v₁. ✓

Part 2: If someone CANNOT reach us → DFS on reversed graph will NOT find them

Proof by contradiction: Assume there is NO path Ewa → our_house on the original graph, but DFS on the reversed graph DOES find Ewa. This means a path our_house → ... → Ewa exists on the reversed graph. But every path on the reversed graph corresponds to a reversed path on the original graph. So Ewa → ... → our_house must exist on the original graph — CONTRADICTION with our assumption! ✗

Conclusion: The set of vertices found by DFS on the reversed graph = exactly the set of vertices that can reach our house. No false positives, no false negatives.

The flip trick is much faster — we run only 2 DFS searches instead of V+1!

Note: This algorithm finds the SCC of only ONE vertex. To find ALL SCCs in a graph, we use Kosaraju's or Tarjan's algorithm — but that's a topic for another lesson!