🔄 Strongly Connected Components Fundamentals

🎯 What are Strongly Connected Components?

A Strongly Connected Component (SCC) of a directed graph is a maximal set of vertices where every vertex is reachable from every other vertex in the set. In other words, there is a directed path both ways between any two vertices in the component.

Maximal: Cannot add more vertices without breaking the property
Mutual Reachability: For any u, v in SCC, u → v and v → u
Partition: SCCs partition the vertices of a directed graph
Algorithms: Kosaraju, Tarjan, Gabow

📌 Mutual Reachability📌 Partition📌 DAG of SCCs

The Core Insight

Key Insight: SCCs reveal the "cyclic structure" of a directed graph. Condensing SCCs into nodes yields a DAG (Directed Acyclic Graph), called the condensation graph.

Three Main Algorithms:

Kosaraju Two-pass DFS, easiest to understand
Tarjan Single-pass DFS, most efficient
Gabow Single-pass, similar to Tarjan

# Strongly Connected Components - Problem Statement
# Given: Directed graph G = (V, E)
# Find: Partition of V into SCCs

# Example:
# Graph with vertices {0, 1, 2, 3, 4, 5, 6}
# Edges: 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 6→4, 6→5
# SCCs: {0,1,2}, {3,4,5}, {6}

# Visualization:
#     0 ←→ 1 ←→ 2
#               ↓
#     3 ←→ 4 ←→ 5
#     ↑         ↑
#     6 ←──────┘

📐 Properties & Definitions

🎯 Key Properties of SCCs

Equivalence Relation: SCCs form equivalence classes under mutual reachability
Condensation DAG: Contracting SCCs yields a DAG (no cycles)
Source SCC: No incoming edges from other SCCs
Sink SCC: No outgoing edges to other SCCs
Singleton SCC: A vertex with no self-loop or cycles

# Understanding SCC Properties

# Example 1: Single cycle
# 1 → 2 → 3 → 1
# SCC: {1, 2, 3} (all vertices mutually reachable)

# Example 2: Two SCCs with edge between
# 1 → 2 → 3 → 1  (SCC A)
# 4 → 5 → 4      (SCC B)
# 1 → 4          (edge from SCC A to SCC B)
# SCCs: {1,2,3}, {4,5}
# Condensation: A → B

# Example 3: Star SCCs
#     1 ←→ 2
#     ↓   ↓
# 3 ←→ 4 ←→ 5
#     ↑   ↑
#     6 ←→ 7
# SCCs: {1,2}, {3,4,5}, {6,7}
# Condensation: {1,2} → {3,4,5} ← {6,7}

🔵 Kosaraju's Algorithm

🎯 Two-Pass DFS Algorithm

Kosaraju's algorithm is the most straightforward SCC algorithm. It performs two DFS passes: one on the original graph to get finishing times, and one on the reversed graph to discover SCCs.

Step 1: DFS on original graph, record finishing order
Step 2: DFS on reversed graph in reverse finishing order
Time: O(V + E)
Space: O(V)

# Kosaraju's Algorithm
from collections import defaultdict

def kosaraju_scc(vertices, edges):
    # Build adjacency list
    adj = defaultdict(list)
    radj = defaultdict(list)  # reversed graph
    
    for u, v in edges:
        adj[u].append(v)
        radj[v].append(u)
    
    visited = set()
    order = []
    
    # Step 1: DFS on original graph to get finishing order
    def dfs1(u):
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                dfs1(v)
        order.append(u)
    
    for v in vertices:
        if v not in visited:
            dfs1(v)
    
    # Step 2: DFS on reversed graph in reverse order
    visited.clear()
    sccs = []
    
    def dfs2(u, scc):
        visited.add(u)
        scc.append(u)
        for v in radj[u]:
            if v not in visited:
                dfs2(v, scc)
    
    for v in reversed(order):
        if v not in visited:
            scc = []
            dfs2(v, scc)
            sccs.append(scc)
    
    return sccs

# Example
vertices = [0, 1, 2, 3, 4, 5, 6]
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 4), (6, 5)]
sccs = kosaraju_scc(vertices, edges)
print(sccs)
# Output: [{0,1,2}, {3,4,5}, {6}]

🟣 Tarjan's Algorithm

🎯 Single-Pass DFS Algorithm

Tarjan's algorithm finds SCCs in a single DFS pass using indices and low-link values. It's more efficient than Kosaraju in practice.

Key Concepts: DFS index, low-link value
Low-link: Smallest index reachable from the node
Time: O(V + E)
Space: O(V)

# Tarjan's Algorithm
def tarjan_scc(vertices, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    index = 0
    indices = {}
    lowlink = {}
    stack = []
    on_stack = set()
    sccs = []
    
    def strongconnect(u):
        nonlocal index
        indices[u] = index
        lowlink[u] = index
        index += 1
        stack.append(u)
        on_stack.add(u)
        
        for v in adj[u]:
            if v not in indices:
                strongconnect(v)
                lowlink[u] = min(lowlink[u], lowlink[v])
            elif v in on_stack:
                lowlink[u] = min(lowlink[u], indices[v])
        
        # If u is the root of an SCC
        if lowlink[u] == indices[u]:
            scc = []
            while True:
                v = stack.pop()
                on_stack.remove(v)
                scc.append(v)
                if v == u:
                    break
            sccs.append(scc)
    
    for v in vertices:
        if v not in indices:
            strongconnect(v)
    
    return sccs

# Example
vertices = [0, 1, 2, 3, 4, 5, 6]
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 4), (6, 5)]
sccs = tarjan_scc(vertices, edges)
print(sccs)
# Output: [{0,1,2}, {3,4,5}, {6}]

🟢 Gabow's Algorithm

🎯 Another Single-Pass DFS Algorithm

Gabow's algorithm is similar to Tarjan's but uses two stacks instead of a stack and index array. It's more space-efficient for some implementations.

Approach: DFS with two stacks (path stack and SCC stack)
Time: O(V + E)
Space: O(V)
Use Case: When you need to avoid recursive DFS

# Gabow's Algorithm (Simplified)
def gabow_scc(vertices, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    index = 0
    indices = {}
    path_stack = []
    scc_stack = []
    sccs = []
    
    def dfs(u):
        nonlocal index
        indices[u] = index
        index += 1
        path_stack.append(u)
        scc_stack.append(u)
        
        for v in adj[u]:
            if v not in indices:
                dfs(v)
            elif indices[v] < indices[u] and v in scc_stack:
                # Back edge to a node in current SCC
                indices[u] = min(indices[u], indices[v])
                while indices[scc_stack[-1]] > indices[u]:
                    scc_stack.pop()
        
        if path_stack[-1] == u:
            path_stack.pop()
        
        if scc_stack[-1] == u:
            scc = []
            while True:
                v = scc_stack.pop()
                scc.append(v)
                if v == u:
                    break
            sccs.append(scc)
    
    for v in vertices:
        if v not in indices:
            dfs(v)
    
    return sccs

# Example
vertices = [0, 1, 2, 3, 4, 5, 6]
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 4), (6, 5)]
sccs = gabow_scc(vertices, edges)
print(sccs)

📊 Condensation Graph (DAG)

🎯 Creating a DAG from SCCs

The condensation graph is formed by contracting each SCC into a single node. The resulting graph is always a DAG.

Nodes: Each SCC becomes a node
Edges: Edge from SCC A to SCC B if there's an edge from any node in A to any node in B
Property: The condensation graph is always acyclic
Applications: Topological sort on SCCs

# Build Condensation Graph
def build_condensation(vertices, edges):
    # Find SCCs using any algorithm
    sccs = kosaraju_scc(vertices, edges)
    
    # Map vertex -> SCC ID
    comp_id = {}
    for i, scc in enumerate(sccs):
        for v in scc:
            comp_id[v] = i
    
    # Build condensation graph
    cond_adj = defaultdict(set)  # Use set to avoid duplicates
    
    for u, v in edges:
        if comp_id[u] != comp_id[v]:
            cond_adj[comp_id[u]].add(comp_id[v])
    
    return comp_id, cond_adj, len(sccs)

# Example
vertices = [0, 1, 2, 3, 4, 5, 6]
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 4), (6, 5)]
comp_id, cond_adj, num_sccs = build_condensation(vertices, edges)

print(f"Number of SCCs: {num_sccs}")
print(f"Component IDs: {comp_id}")
print(f"Condensation edges: {dict(cond_adj)}")
# Output:
# Number of SCCs: 3
# Component IDs: {0: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 2}
# Condensation edges: {0: {1}, 2: {1}}

⚖️ Algorithm Comparison

Feature	Kosaraju	Tarjan	Gabow
Passes	2 passes (DFS)	1 pass (DFS)	1 pass (DFS)
Graph Reversal	Yes	No	No
Time Complexity	O(V + E)	O(V + E)	O(V + E)
Space Complexity	O(V)	O(V)	O(V)
Implementation	Easiest	Moderate	Moderate
Recursion Depth	O(V)	O(V)	O(V)
Memory Overhead	Higher (two graphs)	Lower	Lower
Cache Friendliness	Good	Good	Good

⏱️ Time & Space Complexities

Algorithm	Time Complexity	Space Complexity	Notes
Kosaraju	O(V + E)	O(V + E)	Two graph traversals
Tarjan	O(V + E)	O(V)	Single pass DFS
Gabow	O(V + E)	O(V)	Two stacks
Path-based DFS	O(V + E)	O(V)	Alternative to Tarjan
Condensation	O(V + E)	O(V)	Post-processing

🌍 Real-World Applications

Social Networks: Finding communities (mutual followers)
Web Crawling: Discovering strongly connected web pages
Compiler Optimization: Detecting cycles in dependencies
Circuit Design: Analyzing feedback loops
Data Flow Analysis: Finding loops in control flow graphs
2-SAT Problems: Solving satisfiability problems
Deadlock Detection: Finding cycles in resource allocation graphs
Recommendation Systems: Finding user communities

🧩 2-SAT Problem

🎯 Solving 2-SAT using SCC

2-SAT (2-satisfiability) is a problem where we need to assign boolean values to variables to satisfy a conjunction of clauses, each with 2 literals. SCCs provide an elegant solution.

Approach: Build implication graph, find SCCs
Key Insight: If x and ¬x are in same SCC → unsatisfiable
Solution: Assign values in reverse topological order
Time: O(V + E) after building implication graph

# 2-SAT Solver using SCC
def two_sat(n, clauses):
    # n = number of variables
    # clauses = list of (x, y) where x and y are literals
    # Literal encoding: positive i → i, negative i → ~i
    # We'll use 2*n vertices: i for variable i, i+n for variable i
    
    def var_id(var):
        if var >= 0:
            return var  # positive literal
        else:
            return -var + n  # negative literal
    
    # Build implication graph
    adj = defaultdict(list)
    
    for x, y in clauses:
        # x → y and ¬y → ¬x
        adj[var_id(x)].append(var_id(y))
        adj[var_id(y) + n].append(var_id(x) + n)
    
    # Find SCCs
    vertices = list(range(2 * n))
    edges = [(u, v) for u in adj for v in adj[u]]
    sccs = kosaraju_scc(vertices, edges)
    
    # Check if x and ¬x are in same SCC
    comp_id = {}
    for i, scc in enumerate(sccs):
        for v in scc:
            comp_id[v] = i
    
    for i in range(n):
        if comp_id[i] == comp_id[i + n]:
            return None  # Unsatisfiable
    
    # Build assignment (simplified)
    assignment = {}
    for scc in sccs:
        for v in scc:
            if v < n:
                assignment[v] = True
            else:
                assignment[v - n] = False
    
    return assignment

🧠 Advanced Concepts

Online SCC: Finding SCCs in dynamic graphs
Incremental SCC: Maintaining SCCs when edges are added
Decremental SCC: Maintaining SCCs when edges are removed
SCC in Distributed Systems: Parallel SCC algorithms
SCC in Large Graphs: External memory algorithms
Maximum SCC: Finding the largest SCC

🌀 Variations

Path-Based DFS: Alternative to Tarjan's
Iterative SCC: Non-recursive implementations
SCC with Weights: Weighted SCC analysis
Minimum SCC: Finding minimum size SCC
SCC with Constraints: Constrained SCC problems

📊 Visualization

🎯 Visualizing SCCs

Understanding SCCs through visual representation helps grasp the concept of mutual reachability.

# SCC Visualization Examples

# Example 1: Single SCC (strongly connected)
# 1 → 2 → 3 → 1
# Visualization:
#   1 ←→ 2
#   ↑     ↓
#   3 ←←←←
# SCC: {1,2,3} (all vertices mutually reachable)

# Example 2: Two SCCs
# 1 → 2 → 3 → 1
# 2 → 4 → 5 → 4
# Visualization:
#   {1,2,3} → {4,5}
# SCCs: {1,2,3}, {4,5}
# Condensation: A → B

# Example 3: Complex SCCs
#       0 ←→ 1 ←→ 2
#       ↓         ↓
#       3 ←→ 4 ←→ 5
#       ↑         ↑
#       6 ←→ 7 ←←←←
# SCCs: {0,1,2}, {3,4,5}, {6,7}
# Condensation: A → B ← C

# Kosaraju's Algorithm Visualization:
# Step 1: DFS order on original graph
# Step 2: DFS on reversed graph in reverse order
# Each DFS on reversed graph discovers one SCC

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Find SCCs in a directed graph"
2-SAT: "Solve the 2-SAT problem"
Number of SCCs: "Count the number of SCCs"
Maximum SCC: "Find the largest SCC"
Condensation: "Build the condensation graph"
Path Existence: "Check if path exists between two vertices"
Dominator Analysis: "Find dominators in a flow graph"
Loop Detection: "Detect cycles in a directed graph"

# Interview Problem: Count SCCs
def count_sccs(vertices, edges):
    sccs = kosaraju_scc(vertices, edges)
    return len(sccs)

# Interview Problem: Largest SCC
def largest_scc(vertices, edges):
    sccs = kosaraju_scc(vertices, edges)
    return max(sccs, key=len)

# Interview Problem: Are two vertices in the same SCC?
def same_scc(vertices, edges, a, b):
    sccs = kosaraju_scc(vertices, edges)
    for scc in sccs:
        if a in scc and b in scc:
            return True
    return False

# Interview Problem: 2-SAT Solver
def two_sat_solver(n, clauses):
    # n = number of variables
    # clauses = list of (x, y)
    # Returns assignment or None if unsatisfiable
    pass

# Interview Problem: Find Source SCCs (no incoming edges)
def find_source_sccs(vertices, edges):
    sccs = kosaraju_scc(vertices, edges)
    comp_id = {}
    for i, scc in enumerate(sccs):
        for v in scc:
            comp_id[v] = i
    
    has_incoming = [False] * len(sccs)
    for u, v in edges:
        if comp_id[u] != comp_id[v]:
            has_incoming[comp_id[v]] = True
    
    return [i for i in range(len(sccs)) if not has_incoming[i]]