Advanced Graphs: SCC, Bridges, Articulation Points

Concept

Tarjan's algorithm assigns each node a discovery time and a low-link (the earliest time reachable through its subtree plus one back edge).

Bridge: edge (u, v) where low[v] > disc[u] — removing it disconnects the graph. Articulation point: a node whose removal disconnects the graph.

Strongly connected components (directed graphs) group nodes that can all reach each other; Kosaraju does it with two DFS passes, Tarjan with one and a stack.

Complexity

Code (Python)

def critical_connections(n, connections):
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v); graph[v].append(u)
    disc, low = [-1] * n, [0] * n
    timer, bridges = [0], []

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return bridges

Remember

• low[v] > disc[u] → bridge.
• SCCs condense a directed graph into a DAG.
• Use iterative DFS for very large graphs (recursion limits).