Strongly Connected Components Using DFS 

Strongly Connected Components (SCCs) are a fundamental application of Depth-First Search (DFS) in directed graphs.

1. What is a Strongly Connected Component?

Consider a directed graph:

$$G=(V,E)$$

A set of vertices $C\subseteq V$ is a strongly connected component if every pair of vertices in $C$ can reach each other.

In other words, for every pair of vertices $u,v\in C$:

$$u⇝v$$

and

$$v⇝u$$

where $u⇝v$ means that there is a directed path from u to v.

Simple example

Consider:

A → B
↑   ↓
└── C

There are paths:

A → B
B → C
C → A

Therefore:

• A can reach B, C
• B can reach A, C
• C can reach A, B

Hence:

{A,B,C}​

is one strongly connected component.

---

2. Strongly Connected Does Not Mean Every Pair Has a Direct Edge

This is an important point for students.

Consider:

A → B → C
↑       |
|_______|

There may be no direct edge:

A → C

but there is a path:

A → B → C

Similarly:

C → A

Therefore A and C are still strongly connected.

So SCC is based on reachability through paths, not necessarily direct edges.

---

3. Example with Multiple SCCs

Consider the following directed graph:Let's construct a clearer example:

       A → B
       ↑   ↓
       C ←─┘

       D → E
       ↑   ↓
       F ←─┘

       C → D

Here:

A → B → C → A

forms one SCC:

C1​={A,B,C}

and:

D → E → F → D

forms another:

C2​={D,E,F}

There is an edge:

C → D

connecting the two components.

So the SCCs are:

{A,B,C},{D,E,F}​

---

4. Why Are SCCs Useful?

Many directed-graph problems become easier once the graph is divided into SCCs.

For example, SCCs can represent:

• mutually dependent modules
• groups of web pages with mutual reachability
• cyclic dependencies
• states in finite-state systems
• mutually reachable locations in a network
• dependency cycles in software systems

Instead of processing the entire graph at once, an algorithm can:

1. Find the SCCs.
2. Treat each SCC as a single unit.
3. Analyze the connections between the SCCs.

This produces a much simpler graph called the component graph or SCC graph.

---

5. The Component Graph

Suppose the SCCs are:

C1​={A,B,C}

and

C2​={D,E,F}

with an edge:

C → D

Then we can contract each SCC into a single vertex:

      C₁  ─────→  C₂

where:

C₁ = {A,B,C}
C₂ = {D,E,F}

This graph is called:

GSCC​​

or the component graph.

GSCC​ is always a DAG​

Even though the original graph may contain many cycles inside its SCCs, once each SCC is collapsed into one vertex, there cannot be a cycle between the components.

6. What is the Transpose of a Graph?

The SCC algorithm uses the transpose of G.

The transpose GT is obtained by reversing every directed edge.

If:

A → B

exists in G, then:

A ← B

or:

B → A

exists in GT.

7. Why Does the Transpose Have the Same SCCs?

This is a very important observation.

Suppose in G:

$$u⇝v$$

Then in GT, the same path exists in reverse:

$$v⇝u$$

If in G:

$$u⇝v$$

and

$$v⇝u$$

then in GT:

$$v⇝u$$

and

$$u⇝v$$

Therefore, the mutual-reachability relationship remains unchanged.

Hence:

G and GT have exactly the same SCCs​

The transpose does not change which vertices belong to an SCC.

8. Algorithm for Finding SCCs

The algorithm :

STRONGLY-CONNECTED-COMPONENTS(G)

1. Call DFS(G) to compute finishing times u.f
   for each vertex u.

2. Construct Gᵀ.

3. Call DFS(Gᵀ), but consider vertices in
   decreasing order of their finishing times
   computed in Step 1.

4. Each tree in the DFS forest produced in Step 3
   represents one strongly connected component.

The remarkable idea is:

Two DFS traversals are sufficient to find all strongly connected components.

              Original graph G

                   ↓

                 DFS on G

                    ↓

             Finishing times

                     ↓

            Construct Gᵀ

                   ↓

     Order vertices by decreasing

       finishing time from DFS(G)

                     ↓

              DFS on Gᵀ

                     ↓

       Each DFS tree = one SCC 

9. Complexity Analysis

SCC gives a linear-time algorithm:

Θ(V+E)​

Let's examine each step.

---

Step 1: First DFS

DFS on G:

Θ(V+E)​

---

Step 2: Construct the Transpose

We need to reverse every edge.

For every vertex and every edge, we process it once.

Therefore:

Θ(V+E)​

---

Step 3: Second DFS

DFS is performed on GT.

Since GT has:

V

vertices and:

E

edges,

the second DFS takes:

Θ(V+E)​

---

Step 4: Process Vertices in Finishing-Time Order

The vertices must be considered in decreasing order of their first DFS finishing times.

This can be done efficiently by maintaining an appropriate ordering of the vertices.

The work is:

Θ(V)

which is smaller than the DFS work.

---

10. Total Complexity

Therefore:

T(V,E)​=Θ(V+E)+Θ(V+E)+Θ(V+E)+Θ(V)=Θ(V+E)​

Thus:

SCC algorithm runs in Θ(V+E)​

This is why the algorithm is called a linear-time SCC algorithm.

---

10. Space Complexity

Using adjacency lists:

Original graph

$$\Theta (V+E)$$

Transpose graph

$$\Theta (V+E)$$

DFS attributes

For each vertex:

• color
• predecessor
• discovery time
• finishing time

require:

Θ(V)

Therefore the total space, including the graph and its transpose, is:

Θ(V+E)

​

Summary

The first DFS determines the correct order in which the SCCs should be considered; reversing the edges and performing a second DFS in decreasing finishing-time order causes each DFS tree to capture exactly one strongly connected component.