Strongly Connected Components and Bridges

A strongly connected component (SCC) is a maximal group of nodes in a directed graph where every node can reach every other node in the group, following edge directions both ways. A bridge is the opposite kind of fragility: a single edge in an undirected graph whose removal disconnects the graph. Both questions are answered with the same tool — one DFS pass that tracks when each node was first discovered.

What you’ll learn

What a strongly connected component is, and why it’s a directed-graph concept (undirected connectivity is simpler — everything reachable is automatically “strongly” connected).
Kosaraju’s algorithm: two DFS passes plus a graph transpose.
A pointer to Tarjan’s algorithm — a single-pass alternative using lowlink values.
Bridges: edges whose removal disconnects the graph, found with Tarjan’s discovery-time/lowlink trick.
A quick mention of articulation points, the node-removal analogue of bridges.

Strongly connected components

In a directed graph, “connected” isn’t enough — you need a path u -> vu -> v and a path v -> uv -> u for uu and vv to be in the same SCC. Squash every SCC down to a single “super-node” and the result (the condensation graph) is always a DAG — no cycles can survive between components, otherwise those components would have merged into one.

diagram Directed graph with two SCCs and a tail node mermaid

  graph LR
    N0["0"] --> N1["1"]
    N1 --> N2["2"]
    N2 --> N0
    N1 --> N3["3"]
    N3 --> N4["4"]

diagram Condensation graph: each SCC squashed into one node mermaid

  graph LR
    S0["SCC: (0,1,2)"] --> S1["SCC: (3)"]
    S1 --> S2["SCC: (4)"]

0 -> 1 -> 2 -> 00 -> 1 -> 2 -> 0 is a cycle, so {0, 1, 2}{0, 1, 2} collapses into one SCC. 33 and 44 each sit alone (a single node is trivially its own SCC), and the edges between the three SCCs form a clean DAG.

Kosaraju’s algorithm

Kosaraju’s algorithm finds every SCC in three steps:

Run a DFS over the graph, and record each node in a stack by finish time (append it only after all its descendants are done — postorder).
Build the transpose graph: every edge reversed.
Pop nodes off the finish-time stack (highest finish time first) and run DFS on the transpose. Each DFS tree you get this way is exactly one SCC.

kosaraju_scc.py

def kosaraju_scc(n, edges):
    graph = {i: [] for i in range(n)}
    reverse_graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        reverse_graph[v].append(u)
 
    # Pass 1: record nodes in POSTORDER (finish time) on the original graph.
    visited = [False] * n
    finish_order = []
 
    def dfs1(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs1(neighbor)
        finish_order.append(node)   # append AFTER exploring every descendant
 
    for node in range(n):
        if not visited[node]:
            dfs1(node)
 
    # Pass 2: DFS on the TRANSPOSE, visiting in decreasing finish-time order.
    visited2 = [False] * n
    components = []
 
    def dfs2(node, component):
        visited2[node] = True
        component.append(node)
        for neighbor in reverse_graph[node]:
            if not visited2[neighbor]:
                dfs2(neighbor, component)
 
    for node in reversed(finish_order):
        if not visited2[node]:
            component = []
            dfs2(node, component)
            components.append(component)
 
    return components
 
 
n = 5
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]
print("SCCs:", kosaraju_scc(n, edges))

kosaraju_scc.py

def kosaraju_scc(n, edges):
    graph = {i: [] for i in range(n)}
    reverse_graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        reverse_graph[v].append(u)
 
    # Pass 1: record nodes in POSTORDER (finish time) on the original graph.
    visited = [False] * n
    finish_order = []
 
    def dfs1(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs1(neighbor)
        finish_order.append(node)   # append AFTER exploring every descendant
 
    for node in range(n):
        if not visited[node]:
            dfs1(node)
 
    # Pass 2: DFS on the TRANSPOSE, visiting in decreasing finish-time order.
    visited2 = [False] * n
    components = []
 
    def dfs2(node, component):
        visited2[node] = True
        component.append(node)
        for neighbor in reverse_graph[node]:
            if not visited2[neighbor]:
                dfs2(neighbor, component)
 
    for node in reversed(finish_order):
        if not visited2[node]:
            component = []
            dfs2(node, component)
            components.append(component)
 
    return components
 
 
n = 5
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]
print("SCCs:", kosaraju_scc(n, edges))

Tarjan’s algorithm: the single-pass alternative

Tarjan’s algorithm finds the same SCCs in one DFS pass instead of two, using a low[node]low[node] value — the smallest discovery time reachable from nodenode via any number of tree edges plus at most one back edge. A node starts a new SCC exactly when low[node] == disc[node]low[node] == disc[node] (nothing below it reaches further back than itself). It needs an explicit stack of “currently active” nodes instead of a transpose graph — more fiddly to implement correctly, but avoids building a second graph. The lowlink idea it introduces is exactly what powers bridge-finding next.

Bridges: edges that hold the graph together

A bridge is an edge whose removal increases the number of connected components. Tarjan’s lowlink answers this directly on an undirected graph: track each node’s discovery time disc[node]disc[node] and its low[node]low[node] (the earliest discovery time reachable from its subtree via one back edge). An edge (node, neighbor)(node, neighbor) in the DFS tree is a bridge exactly when low[neighbor] > disc[node]low[neighbor] > disc[node] — meaning nothing in neighborneighbor’s subtree can reach nodenode or anything before it except through that one edge.

find_bridges.py

def find_bridges(n, edges):
    graph = {i: [] for i in range(n)}
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))   # store the edge's index to skip its own reverse
 
    disc = [-1] * n
    low = [0] * n
    timer = [0]
    bridges = []
 
    def dfs(node, parent_edge):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        for neighbor, edge_id in graph[node]:
            if edge_id == parent_edge:
                continue                      # don't walk back over the edge we just used
            if disc[neighbor] == -1:
                dfs(neighbor, edge_id)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > disc[node]:
                    bridges.append(edges[edge_id])
            else:
                low[node] = min(low[node], disc[neighbor])
 
    for node in range(n):
        if disc[node] == -1:
            dfs(node, -1)
 
    return bridges
 
 
# Two triangles (0-1-2 and 3-4-5) joined by a single connecting edge.
n = 6
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)]
print("bridges:", find_bridges(n, edges))

find_bridges.py

def find_bridges(n, edges):
    graph = {i: [] for i in range(n)}
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))   # store the edge's index to skip its own reverse
 
    disc = [-1] * n
    low = [0] * n
    timer = [0]
    bridges = []
 
    def dfs(node, parent_edge):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        for neighbor, edge_id in graph[node]:
            if edge_id == parent_edge:
                continue                      # don't walk back over the edge we just used
            if disc[neighbor] == -1:
                dfs(neighbor, edge_id)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > disc[node]:
                    bridges.append(edges[edge_id])
            else:
                low[node] = min(low[node], disc[neighbor])
 
    for node in range(n):
        if disc[node] == -1:
            dfs(node, -1)
 
    return bridges
 
 
# Two triangles (0-1-2 and 3-4-5) joined by a single connecting edge.
n = 6
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)]
print("bridges:", find_bridges(n, edges))

Neither triangle has a bridge — every node inside one has two disjoint ways back to any other node in it. The single edge (2, 3)(2, 3) connecting the two triangles is the only bridge: cut it, and the graph splits in two.

Complexity

Kosaraju’s algorithm is two DFS passes plus building the transpose: $O(V + E)$ time, $O(V + E)$ space. Tarjan’s SCC algorithm and the bridge-finding DFS are both a single pass: $O(V + E)$ time, $O(V)$ space for discdisc/lowlow.

Practice — real LeetCode problems

A reachability closure to warm up, then Tarjan’s bridge-finding algorithm — the one worth memorising — and finally a problem where recognising that the answer is always 0, 1 or 2 beats any clever algorithm.

LC 1462 — Course Schedule IV · Medium

Problem. Given numCoursesnumCourses courses and direct prerequisite pairs [a, b][a, b] meaning aa must be taken before bb, answer each query [u, v][u, v]: is uu a prerequisite of vv, directly or indirectly?

Constraints. 2 <= numCourses <= 1002 <= numCourses <= 100, 0 <= len(prerequisites) <= n*(n-1)/20 <= len(prerequisites) <= n*(n-1)/2, 1 <= len(queries) <= 10**41 <= len(queries) <= 10**4, the graph is a DAG with no duplicate edges.

Examples. n = 2n = 2, prerequisites = [[1,0]]prerequisites = [[1,0]], queries = [[0,1],[1,0]]queries = [[0,1],[1,0]] gives [false,true][false,true] · with no prerequisites, everything is falsefalse

Editorial · approach, complexity, follow-ups

The shape of the constraints picks the algorithm. A hundred nodes but ten thousand queries means precompute once, answer instantly — a BFS per query would be $10^4$ traversals for no reason.

Time $O(n^3 + Q)$ , about $10^6$ here. Space $O(n^2)$ .

kk must be the outermost loop. This is the one thing to get right about Floyd-Warshall. The invariant after iteration kk is “reach[i][j] is correct using only intermediates from the first kk nodes”, and any other loop order destroys it. Being able to state that invariant is what distinguishes understanding it from having copied it.
The if reach[i][k]if reach[i][k] guard is not just a speedup — it keeps the inner loop off entirely for most pairs, which matters at $n^3$ .
Direction matters. [a, b][a, b] means aa before bb, so seed reach[a][b]reach[a][b], and a query [u, v][u, v] asks reach[u][v]reach[u][v]. Reversing it passes the second test and fails the first, which is why both are in the tests.
No prerequisites means everything is FalseFalse, and the closure of an empty relation is empty.
reach[i][i]reach[i][i] stays FalseFalse, which is right for a DAG — a course is not its own prerequisite.

The alternative worth mentioning: a topological order plus a bitmask per node, propagating ancestor sets with ancestors[v] |= ancestors[u] | (1 << u)ancestors[v] |= ancestors[u] | (1 << u). With Python’s big integers that is $O(n^2)$ word operations and considerably faster in practice.

Follow-ups you should expect: “The graph might have cycles?” — then compute SCCs first and run the closure on the condensation, since everything in one SCC reaches everything else in it. ” $n = 10^5$ ?” — $O(n^2)$ memory is already too much; you would answer queries individually or restrict to tree-shaped input. “Prerequisites added over time?” — incremental closure, updating one row and column per new edge. “The shortest prerequisite chain?” — BFS instead of a boolean closure, or Floyd-Warshall over distances.

LC 1192 — Critical Connections in a Network · Hard

Problem. Given a connected undirected network of nn servers and their connections, return all critical connections — edges whose removal would disconnect some server from the rest. Any order.

Constraints. 2 <= n <= 10**52 <= n <= 10**5, n - 1 <= len(connections) <= 10**5n - 1 <= len(connections) <= 10**5, no repeated connections, the graph is connected.

Examples. n = 4n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]connections = [[0,1],[1,2],[2,0],[1,3]] gives [[1,3]][[1,3]] — the triangle has no critical edge · n = 2n = 2, [[0,1]][[0,1]] gives [[0,1]][[0,1]]

Editorial · approach, complexity, follow-ups

Tarjan’s bridge algorithm. One DFS, two arrays, and one comparison — but only if you know what the arrays mean.

disc[v]disc[v] — when the DFS first reached vv. A timestamp; it never changes.
low[v]low[v] — the smallest discdisc reachable from vv’s DFS subtree using tree edges downward plus at most one back edge.

The bridge condition low[child] > disc[node]low[child] > disc[node] then reads directly: nothing in the child’s subtree can reach nodenode or anything discovered before it by any route other than this edge. Cut it and the subtree is stranded. Compare with the articulation-point condition low[child] >= disc[node]low[child] >= disc[node], which differs by one character and answers a different question — that pairing is a favourite interview probe.

Time $O(n + E)$ . Space $O(n + E)$ .

Use disc[nxt]disc[nxt], not low[nxt]low[nxt], for a back edge. Taking lowlow would let two back edges chain together, which is precisely what lowlow is defined to forbid, and you would miss bridges. Subtle and very commonly wrong.
Skipping the parent by node id is fine here because the constraints promise no repeated connections. With parallel edges it breaks — two edges between the same pair mean neither is a bridge, yet skipping by node id hides the second one. Track the incoming edge index instead. Say this out loud; it is the most valuable thing you can add to a correct answer.
A tree has every edge critical; a cycle has none. Those are the two extremes, and the triangle case in the tests is the “none” check.
Recursion depth. At $n = 10^5$ a path-shaped graph blows Python’s default limit of 1000. In an interview say you would raise the limit or write it iteratively; the recursive version is what gets discussed.
The graph is promised connected, so one dfs(0, -1)dfs(0, -1) suffices. If it were not, loop over all unvisited nodes.

Follow-ups you should expect: “Articulation points (cut vertices) instead?” — same DFS, condition low[child] >= disc[node]low[child] >= disc[node] for non-root nodes, and the root is a cut vertex exactly when it has more than one DFS child. “Directed graphs and SCCs?” — Tarjan’s SCC algorithm reuses discdisc/lowlow with an explicit stack, or use Kosaraju’s two passes, which is easier to explain. “2-edge-connected components?” — remove the bridges and take the remaining components. “Which single edge addition minimises the bridges?” — contract the 2-edge-connected components into a tree and add an edge between two leaves at maximum distance.

LC 1568 — Minimum Number of Days to Disconnect Island · Hard

Problem. A binary grid where 1 is land. The grid is connected if it has exactly one island. In one day you may change a single 1 into a 0. Return the minimum number of days to make the grid disconnected — zero islands or more than one.

Constraints. 1 <= rows, cols <= 301 <= rows, cols <= 30, entries are 0 or 1.

Examples. [[0,1,1,0],[0,1,1,0],[0,0,0,0]][[0,1,1,0],[0,1,1,0],[0,0,0,0]] gives 22 · [[1,1]][[1,1]] gives 22 · [[1,0,1,0]][[1,0,1,0]] gives 00 — already two islands

Editorial · approach, complexity, follow-ups

The insight is not an algorithm, it is a bound: the answer is never more than 2.

Why. If the island has at least three cells, pick the topmost row it occupies and the leftmost cell in that row. That cell has land in at most two of its four directions — nothing above and nothing to the left, by construction. Remove those one or two neighbours and the cell is isolated, giving at least two islands. Grids with one or two cells are the small cases: a single cell takes 1 day (removing it leaves zero islands), and two adjacent cells take 2.

With the answer bounded, the search is trivial: check 0, then check 1 by trying every removal, otherwise answer 2.

Time $O((rc)^2)$ — up to 900 candidate removals, each followed by an $O(rc)$ recount, so about $8 \times 10^5$ cell visits. Fine at 30 x 3030 x 30. Space $O(rc)$ .

Zero islands counts as disconnected. An all-water grid answers 0, and a single land cell answers 1 — removing it leaves zero islands, which satisfies “not exactly one”.
Restore the cell after every trial, including on the early return, or the caller sees a mutated grid.
[[1,1]][[1,1]] answers 2, not 1: removing either cell leaves exactly one island, so no single day works.
Already disconnected input short-circuits to 0 before any trial. That check must come first.
Iterative flood fill. At 30 x 3030 x 30 recursion would survive, but the loop costs nothing extra and removes the worry.

Follow-ups you should expect: “Faster than $O((rc)^2)$ ?” — yes: a single land cell whose removal disconnects the island is an articulation point of the grid graph, so one Tarjan pass finds all of them in $O(rc)$ . That is the intended “good” answer and ties this page together — but mind the degenerate cases, since one- and two-cell islands have no articulation point yet still answer 1 and 2. “Prove the bound of 2?” — the topmost-leftmost argument above. “8-directional connectivity?” — the bound rises, since a corner cell can have three neighbours. “Disconnect into exactly kk islands?” — a much harder problem, with no small bound. “Remove water cells to connect instead?” — that is a shortest-path or minimum-cost problem, not this one.

LeetCode problem set

#	Problem	Difficulty	The twist
1192	Critical Connections in a Network	Hard	Exactly the bridge-finding DFS above, applied to server connections
—	Number of SCCs (classic)	—	(concept) — count how many components Kosaraju’s or Tarjan’s algorithm returns; a staple CP exercise more than a named LeetCode problem
—	Strongly Connected Components (classic)	—	The general GfG/CP-judge framing of Kosaraju’s or Tarjan’s algorithm on a raw edge list

Recap

An SCC is a maximal set of directed nodes that can all reach each other; squashing every SCC always yields a DAG (the condensation graph).
Kosaraju’s algorithm: DFS for finish order, transpose the graph, DFS again in decreasing finish-time order — each tree is one SCC. Tarjan’s algorithm does it in one pass using lowlink values.
A bridge is a DFS tree edge where low[neighbor] > disc[node]low[neighbor] > disc[node] — nothing past it can reach back. Articulation points use the same discdisc/lowlow values with a looser (>=>=) comparison.
All of these run in $O(V + E)$ time — the cost is in getting the bookkeeping (finish order, transpose, or lowlink) exactly right, not in the asymptotic complexity.

Next: Maximum Flow — when edges carry capacities instead of just existing, and the question becomes “how much can flow from source to sink.”

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Strongly Connected Components and Bridges

What you’ll learn

Strongly connected components

Kosaraju’s algorithm

Tarjan’s algorithm: the single-pass alternative

Bridges: edges that hold the graph together

Complexity

Practice — real LeetCode problems

LC 1462 — Course Schedule IV · Medium

LC 1192 — Critical Connections in a Network · Hard

LC 1568 — Minimum Number of Days to Disconnect Island · Hard

LeetCode problem set

Recap

Was this page helpful?