Tarjan's Algorithm Intro

Intro

Tarjan's Algorithm is used to find Strongly Connected Components (SCCs) in a directed groups.

SCC: a maximal subset of vertices where every vertex is reachable from every other vertex in the subset

It uses DFS and low link values to efficiently detect SCCs in O(V + E) time.

Graph Requirements

Directed Graphs
Can have cycles, Tarjan will identify them as SCCs
Represented Using:
- Adjacency List
- Edge List

Output

List of SCCs, each being a set of vertices

Vertices in each SCC are mutually reachable

Video Animation

Tarjan: https://www.youtube.com/watch?v=_1TDxihjtoE

Pseudo Code

    def tarjan_scc(graph):

        index = 0
        indices = {}
        lowlink = {}
        stack = []
        on_stack = set()
        sccs = []

        def dfs(v):
            nonlocal index
            indices[v] = index
            lowlink[v] = index
            index += 1
            stack.append(v)
            on_stack.add(v)

            for w in graph[v]:
                if w not in indices:
                    dfs(w)
                    lowlink[v] = min(lowlink[v], lowlink[w])
                elif w in on_stack:
                    lowlink[v] = min(lowlink[v], indices[w])

            # If node is root of SCC
            if lowlink[v] == indices[v]:
                scc = []
                while True:
                    w = stack.pop()
                    on_stack.remove(w)
                    scc.append(w)
                    if w == v:
                        break
                sccs.append(scc)

        for node in graph:
            if node not in indices:
                dfs(node)

        return sccs

Time Complexity

Each vertex visited once Each edge processed once

O(V + E)

Space Complexity

Stack: O(V) Indices and low link arrays: O(V)

IRL Use Case

Compiler Optimization Detect mutually dependent modules or functions
Network Connectivity Analysis Identify clusters where every node can reach every other node

1192. Critical Connections in a Network ::1:: - Hard

Topics: Depth First Search, Graph Theory, Biconnected Component

Intro

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network. A critical connection is a connection that, if removed, will make some servers unable to reach some other server. Return all critical connections in the network in any order.

Example Input	Output
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]	[[1,3]]
n = 2, connections = [[0,1]]	[[0,1]]

Constraints:

2 ≤ n ≤ 10^5

n-1 ≤ connections.length ≤ 10^5

0 ≤ ai, bi ≤ n-1

ai != bi

Abstraction

Find the number of SCC and determine the number of critical connections between them

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [Tarjan] Tarjan Solutions Bridges In Undirected Graph - Advanced Graphs/Advanced Graphs

    def criticalConnections(n: int, connections: list[list[int]]) -> list[list[int]]:
        
        # Build the graph (undirected)
        # graph[u] = list of neighbors
        graph = defaultdict(list)
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        # Initialize Tarjan bookkeeping arrays
        disc = [-1] * n      # discovery times of nodes
        low = [-1] * n       # lowest discovery time reachable from the node
        time = [0]           # global timestamp counter (wrapped in list to mutate)
        res = []             # store critical connections (bridges)
        
        # Define DFS
        def dfs(u, parent):

            disc[u] = low[u] = time[0]    # set discovery & low-link to current time
            time[0] += 1                  # increment global time
            
            # Process all neighbors
            for v in graph[u]:
                if v == parent:
                    # Ignore the edge back to parent
                    continue
                
                if disc[v] == -1:
                    # Neighbor not visited → recurse
                    dfs(v, u)
                    
                    # After returning from recursion:
                    # Update low-link of u based on subtree rooted at v
                    low[u] = min(low[u], low[v])
                    
                    # Tarjan Bridge Condition:
                    # If low[v] > disc[u], edge u-v is a bridge
                    if low[v] > disc[u]:
                        res.append([u, v])
                
                else:
                    # Neighbor already visited → update low-link using back-edge
                    low[u] = min(low[u], disc[v])
        
        # Run DFS from node 0 (graph is connected by problem statement)
        dfs(0, -1)
        
        # Return list of critical connections (bridges)
        return res

LeetCode: Graphs II Tarjan SCC