SyntaxPilot
Courses/DSA and Coding Problems/Lesson 58
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 58 of 90

Strongly connected components and bridges (hard)

queued

These are the notes for DSA episode 58, two hard graph ideas in one episode. Part 1: a city of one-way streets; which junctions can reach each other and come back? Those groups are strongly connected components (SCCs). The obvious way (a forward and a backward search from every junction) is correct but O(V · (V + E)): Time Limit Exceeded on a 1,00,000-junction road. Kosaraju's algorithm finds every group with two depth-first searches, and along the way we hit a real StackOverflowError and fix it. Part 2: two-way roads; which single road closure cuts the city in two? Those roads are bridges (LeetCode 1192, Critical Connections in a Network). Removing each road and re-checking is O(E · (V + E)): Time Limit Exceeded again. Discovery times and low-link values find every bridge in one DFS. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

Part 1. An old city centre is full of one-way streets. From one junction you can often drive to another, but not always back. The traffic police want zones: groups of junctions where a patrol car can get from any junction to any other and return. Between zones, the trip may be one way only.

Part 2. Now every road is two-way and the city is connected. A road closes for repairs. Usually traffic finds a detour, but some roads have none, like the only bridge over a river. Data centres ask the same thing about cables between servers.

In the city In code
A junction / server a node 0 … n-1
A one-way street a directed edge u → v
A zone (there and back) a strongly connected component
A two-way road / cable an undirected edge u - v
A road with no detour a bridge (critical connection)

Every word, from zero

  • Directed graph: edges have a direction, u → v (one-way streets). Undirected: edges go both ways.
  • Reachable: there is a path from u to v following edge directions.
  • Strongly connected component (SCC): a largest set of nodes where every node can reach every other. Each node is in exactly one SCC (possibly alone).
  • Reversed graph (transpose): the same edges with every direction flipped.
  • DFS (depth-first search): go deep, then backtrack. A node is finished when all its neighbours have been explored.
  • Finish order: the order in which DFS finishes nodes. Pushing each finished node on a stack puts the last-finished on top.
  • Condensation: shrink every SCC to one node; the result is always a DAG (directed acyclic graph). A source SCC has no edges coming in from other SCCs; a sink has none going out.
  • Kosaraju's algorithm: DFS for finish order, then DFS on the reversed graph in reverse finish order; each second-pass DFS is one SCC (named after S. Rao Kosaraju).
  • Call stack, stack overflow: each method call uses some stack memory; a recursion one lakh calls deep can run out: java.lang.StackOverflowError.
  • Bridge (critical connection): an edge whose removal disconnects the graph.
  • DFS tree, tree edge, back edge: the edges DFS walks down form a tree; any other edge (to a node seen earlier) is a back edge: a detour.
  • Discovery time disc[u]: when DFS first reaches u (0, 1, 2, …).
  • Low-link low[u]: the smallest discovery time reachable from u's DFS subtree using tree edges downward plus at most one back edge.
  • Articulation point (cut vertex): a node whose removal disconnects the graph.

Part 1: strongly connected components

Problem

Given n nodes and directed edges, count the SCCs.

n edges Answer
5 1→0, 0→2, 2→1, 0→3, 3→4 3: {0, 1, 2}, {3}, {4}
4 0→1, 1→2, 2→3, 3→0 1: a ring
3 none 3: every node alone

Obvious idea: search forwards and backwards from every junction

fwd = everything u reaches (BFS); back = everything that reaches u (BFS on the reversed graph). u's group is fwd ∩ back.

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean reverse) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) {
            if (reverse) g.get(e[1]).add(e[0]);
            else g.get(e[0]).add(e[1]);
        }
        return g;
    }
    static boolean[] reach(List<List<Integer>> g, int s) {
        boolean[] seen = new boolean[g.size()];
        Deque<Integer> q = new ArrayDeque<>();
        q.add(s);
        seen[s] = true;
        while (!q.isEmpty())
            for (int v : g.get(q.poll()))
                if (!seen[v]) { seen[v] = true; q.add(v); }
        return seen;
    }
    static int countSCC(int n, int[][] edges) {
        List<List<Integer>> g = build(n, edges, false), r = build(n, edges, true);
        boolean[] done = new boolean[n];
        int count = 0;
        for (int u = 0; u < n; u++) {
            if (done[u]) continue;
            boolean[] fwd = reach(g, u), back = reach(r, u);
            for (int v = 0; v < n; v++)
                if (fwd[v] && back[v]) done[v] = true;
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        int[][] e1 = {{1, 0}, {0, 2}, {2, 1}, {0, 3}, {3, 4}};
        int[][] e2 = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
        System.out.println(countSCC(5, e1));
        System.out.println(countSCC(4, e2));
        System.out.println(countSCC(3, new int[][]{}));
    }
}
3
1
3

Correct. Now a one-way road of 1,00,000 junctions (i → i + 1):

        int n = 100000;
        int[][] edges = new int[n - 1][];
        for (int i = 0; i + 1 < n; i++) edges[i] = new int[]{i, i + 1};
        long t0 = System.nanoTime();
        int c = countSCC(n, edges);
        System.out.println(c + " groups, " + (System.nanoTime() - t0) / 1000000 + " ms");

Result: Time Limit Exceeded. Every junction is its own group, so we run two searches from every one: O(V · (V + E)) ≈ 1 lakh × 2 lakh = 2,000 crore steps.

The key insight: Kosaraju's two passes

  1. Pass 1: DFS over the whole graph; push each node on a stack when it finishes. On the example (DFS from 0 goes 0 → 2 → 1, then 0 → 3 → 4) the finish order is 1, 2, 4, 3, 0.
  2. Why the last finisher matters: the node that finishes last lies in a source SCC of the condensation (no other group's edges lead into it). Here: 0, in {0, 1, 2}.
  3. Pass 2: reverse every edge. A source group becomes a sink: the edges that used to leave it (0 → 3) now point in (3 → 0), so a DFS from 0 on the reversed graph is trapped inside {0, 1, 2}.
  4. Pop nodes in finish order; each DFS from an unvisited node on the reversed graph is exactly one SCC: {0, 1, 2}, then {3}, then {4}.

Two full DFS passes: O(V + E).

Solution in Java: Kosaraju

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean reverse) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) {
            if (reverse) g.get(e[1]).add(e[0]);
            else g.get(e[0]).add(e[1]);
        }
        return g;
    }
    static List<List<Integer>> g, r;
    static boolean[] seen;
    static Deque<Integer> order;
    static int countSCC(int n, int[][] edges) {
        g = build(n, edges, false);
        r = build(n, edges, true);
        seen = new boolean[n];
        order = new ArrayDeque<>();
        for (int u = 0; u < n; u++)
            if (!seen[u]) dfs1(u);
        seen = new boolean[n];
        int count = 0;
        while (!order.isEmpty()) {
            int u = order.pop();
            if (!seen[u]) { dfs2(u); count++; }
        }
        return count;
    }
    static void dfs1(int u) {
        seen[u] = true;
        for (int v : g.get(u)) if (!seen[v]) dfs1(v);
        order.push(u);
    }
    static void dfs2(int u) {
        seen[u] = true;
        for (int v : r.get(u)) if (!seen[v]) dfs2(v);
    }
    public static void main(String[] args) {
        int[][] e1 = {{1, 0}, {0, 2}, {2, 1}, {0, 3}, {3, 4}};
        int[][] e2 = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
        System.out.println(countSCC(5, e1));
        System.out.println(countSCC(4, e2));
        System.out.println(countSCC(3, new int[][]{}));
    }
}
3
1
3

A real StackOverflowError, and two fixes

On the 1,00,000-junction road, dfs1 calls itself 1,00,000 deep. In the compiler (default stack):

Exception in thread "main" java.lang.StackOverflowError
    at Main.dfs1(Main.java:33)
    at Main.dfs1(Main.java:33)
    at Main.dfs1(Main.java:33)
    ...

Fix 1: a thread with a big stack. The fourth argument of this Thread constructor is the stack size in bytes; 1 << 28 = 256 MB:

    static void run() {
        // ... the big test ...
    }
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(null, Main::run, "big-stack", 1 << 28);
        t.start();
        t.join();
    }
100000 groups, 167 ms

Fix 2: your own stack (no recursion). Keep (node, next-neighbour index) pairs on an explicit stack:

import java.util.*;

public class Main {
    // Kosaraju with explicit stacks: no recursion, so no StackOverflowError on deep graphs.
    static int countSCC(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>(), r = new ArrayList<>();
        for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); r.add(new ArrayList<>()); }
        for (int[] e : edges) { g.get(e[0]).add(e[1]); r.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        int[] order = new int[n], idx = new int[n], stack = new int[n];
        int done = 0;
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            int top = 0;
            stack[top++] = s;
            seen[s] = true;
            while (top > 0) {
                int u = stack[top - 1];
                if (idx[u] < g.get(u).size()) {
                    int v = g.get(u).get(idx[u]++);
                    if (!seen[v]) { seen[v] = true; stack[top++] = v; }
                } else {
                    order[done++] = u;   // u is finished
                    top--;
                }
            }
        }
        Arrays.fill(seen, false);
        int count = 0;
        for (int k = n - 1; k >= 0; k--) {
            int s = order[k];
            if (seen[s]) continue;
            count++;
            int top = 0;
            stack[top++] = s;
            seen[s] = true;
            while (top > 0) {
                int u = stack[--top];
                for (int v : r.get(u)) if (!seen[v]) { seen[v] = true; stack[top++] = v; }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countSCC(5, new int[][]{{1, 0}, {0, 2}, {2, 1}, {0, 3}, {3, 4}}));
        int n = 100000;
        int[][] edges = new int[n - 1][];
        for (int i = 0; i + 1 < n; i++) edges[i] = new int[]{i, i + 1};
        System.out.println(countSCC(n, edges) + " groups");
    }
}
3
100000 groups

The same SCC solution in C++

#include <bits/stdc++.h>
using namespace std;

// Kosaraju: pass 1 records finish order (iterative DFS); pass 2 walks the reversed graph in reverse finish order.
int countSCC(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> g(n), r(n);
    for (auto [a, b] : edges) { g[a].push_back(b); r[b].push_back(a); }
    vector<int> order, idx(n, 0);
    vector<bool> seen(n, false);
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        vector<int> st = {s};
        seen[s] = true;
        while (!st.empty()) {
            int u = st.back();
            if (idx[u] < (int)g[u].size()) {
                int v = g[u][idx[u]++];
                if (!seen[v]) { seen[v] = true; st.push_back(v); }
            } else { order.push_back(u); st.pop_back(); }
        }
    }
    fill(seen.begin(), seen.end(), false);
    int count = 0;
    for (int k = n - 1; k >= 0; k--) {
        int s = order[k];
        if (seen[s]) continue;
        count++;
        vector<int> st = {s};
        seen[s] = true;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (int v : r[u]) if (!seen[v]) { seen[v] = true; st.push_back(v); }
        }
    }
    return count;
}

int main() {
    cout << countSCC(5, {{1, 0}, {0, 2}, {2, 1}, {0, 3}, {3, 4}}) << "\n";
    cout << countSCC(4, {{0, 1}, {1, 2}, {2, 3}, {3, 0}}) << "\n";
    cout << countSCC(3, {}) << "\n";
}
3
1
3

The same SCC solution in Python

# Kosaraju with explicit stacks (Python's recursion limit is about 1000 by default).
def count_scc(n, edges):
    g = [[] for _ in range(n)]
    r = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        r[b].append(a)
    seen, order, idx = [False] * n, [], [0] * n
    for s in range(n):
        if seen[s]:
            continue
        stack, seen[s] = [s], True
        while stack:
            u = stack[-1]
            if idx[u] < len(g[u]):
                v = g[u][idx[u]]
                idx[u] += 1
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
            else:
                order.append(u)
                stack.pop()
    seen, count = [False] * n, 0
    for s in reversed(order):
        if seen[s]:
            continue
        count += 1
        stack, seen[s] = [s], True
        while stack:
            u = stack.pop()
            for v in r[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
    return count

print(count_scc(5, [(1, 0), (0, 2), (2, 1), (0, 3), (3, 4)]))
print(count_scc(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))
print(count_scc(3, []))
print(count_scc(100000, [(i, i + 1) for i in range(99999)]))
3
1
3
100000

Part 2: bridges (LeetCode 1192)

Problem

Critical Connections in a Network. n servers 0 … n-1, undirected connections[i] = [a, b], the network is connected. Return all critical connections (any order).

n connections Answer
4 [[0,1],[1,2],[2,0],[1,3]] [[1,3]]
2 [[0,1]] [[0,1]]

Constraints: 2 ≤ n ≤ 10^5, n - 1 ≤ connections.length ≤ 10^5, no repeated connections.

Obvious idea: remove each road and check

import java.util.*;

public class Main {
    static int count(List<List<Integer>> g, int s) {
        boolean[] seen = new boolean[g.size()];
        Deque<Integer> q = new ArrayDeque<>();
        q.add(s);
        seen[s] = true;
        int c = 1;
        while (!q.isEmpty())
            for (int v : g.get(q.poll()))
                if (!seen[v]) { seen[v] = true; q.add(v); c++; }
        return c;
    }
    static List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> res = new ArrayList<>();
        for (int skip = 0; skip < connections.size(); skip++) {
            List<List<Integer>> g = new ArrayList<>();
            for (int i = 0; i < n; i++) g.add(new ArrayList<>());
            for (int k = 0; k < connections.size(); k++) {
                if (k == skip) continue;
                int a = connections.get(k).get(0), b = connections.get(k).get(1);
                g.get(a).add(b);
                g.get(b).add(a);
            }
            if (count(g, 0) < n) res.add(connections.get(skip));
        }
        return res;
    }
    public static void main(String[] args) {
        var c1 = List.of(List.of(0, 1), List.of(1, 2), List.of(2, 0), List.of(1, 3));
        System.out.println(criticalConnections(4, c1));
        System.out.println(criticalConnections(2, List.of(List.of(0, 1))));
    }
}
[[1, 3]]
[[0, 1]]

On a road of 1,00,000 junctions (every road a bridge): Time Limit Exceeded: one full BFS per road, O(E · (V + E)).

  • disc[u]: when DFS first reaches u.
  • low[u]: the smallest disc that u or anything below it in the DFS tree can reach with tree edges down plus one back edge (a detour).
  • A tree edge u - v (v is u's child) is a bridge exactly when low[v] > disc[u]: nothing under v has a detour back to u or above.

By hand on example 1 (DFS 0 → 1 → 2, back edge 2 - 0, then 1 → 3):

Node disc low Why
0 0 0 start
1 1 0 its child 2 has low 0
2 2 0 back edge to 0
3 3 3 no other road

low[3] = 3 > disc[1] = 1: 1 - 3 is a bridge. low[1] = 0 is not > disc[0] = 0: 0 - 1 is safe (detour through 2). low[2] = 0 is not > disc[1] = 1: safe.

This low-link idea is Robert Tarjan's (1970s).

Solution in Java: one DFS

import java.util.*;

public class Main {
    static List<List<Integer>> adj, res;
    static int[] disc, low;
    static int timer;
    static List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (List<Integer> c : connections) {
            adj.get(c.get(0)).add(c.get(1));
            adj.get(c.get(1)).add(c.get(0));
        }
        disc = new int[n];
        low = new int[n];
        Arrays.fill(disc, -1);
        timer = 0;
        res = new ArrayList<>();
        dfs(0, -1);
        return res;
    }
    static void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) res.add(List.of(u, v));
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
    static void run() {
        var c1 = List.of(List.of(0, 1), List.of(1, 2), List.of(2, 0), List.of(1, 3));
        System.out.println(criticalConnections(4, c1));
        System.out.println(criticalConnections(2, List.of(List.of(0, 1))));
        var ring = List.of(List.of(0, 1), List.of(1, 2), List.of(2, 0));
        var two = List.of(List.of(0, 1), List.of(1, 2), List.of(2, 0),
                List.of(3, 4), List.of(4, 5), List.of(5, 3), List.of(2, 3));
        System.out.println(criticalConnections(3, ring));
        System.out.println(criticalConnections(6, two));
    }
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(null, Main::run, "big-stack", 1 << 28);
        t.start();
        t.join();
    }
}
[[1, 3]]
[[0, 1]]
[]
[[2, 3]]

On the 1,00,000-junction road: 99999 bridges, 264 ms (times vary).

v == parent skips the edge we arrived on. That's safe here because LeetCode 1192 has no repeated connections; with parallel edges, skip the parent edge id instead of the parent node.

The same bridge solution in C++

#include <bits/stdc++.h>
using namespace std;

// Critical Connections (LeetCode 1192): bridges with discovery time and low-link, one DFS.
vector<vector<int>> adj, res;
vector<int> disc, low;
int timer_ = 0;

void dfs(int u, int parent) {
    disc[u] = low[u] = timer_++;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (disc[v] == -1) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) res.push_back({u, v});
        } else low[u] = min(low[u], disc[v]);
    }
}

vector<vector<int>> criticalConnections(int n, vector<vector<int>> connections) {
    adj.assign(n, {}); res.clear();
    for (auto& c : connections) { adj[c[0]].push_back(c[1]); adj[c[1]].push_back(c[0]); }
    disc.assign(n, -1); low.assign(n, 0); timer_ = 0;
    dfs(0, -1);
    return res;
}

void show(const vector<vector<int>>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << "[" << v[i][0] << ", " << v[i][1] << "]";
    cout << "]\n";
}

int main() {
    show(criticalConnections(4, {{0, 1}, {1, 2}, {2, 0}, {1, 3}}));
    show(criticalConnections(2, {{0, 1}}));
    show(criticalConnections(3, {{0, 1}, {1, 2}, {2, 0}}));
    show(criticalConnections(6, {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3}, {2, 3}}));
}
[[1, 3]]
[[0, 1]]
[]
[[2, 3]]

(In C++ the default stack is usually 8 MB on Linux, enough for this DFS on 1 lakh nodes in most judges; an iterative DFS is the safe choice everywhere.)

The same bridge solution in Python (iterative)

# Critical Connections (LeetCode 1192): disc/low with an explicit stack (no recursion limit problems).
def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append(b)
        adj[b].append(a)
    disc, low, res, timer = [-1] * n, [0] * n, [], 0
    disc[0] = low[0] = 0
    timer = 1
    stack = [(0, -1, 0)]          # (node, parent, index of the next neighbour)
    while stack:
        u, parent, i = stack.pop()
        if i < len(adj[u]):
            stack.append((u, parent, i + 1))
            v = adj[u][i]
            if v == parent:
                continue
            if disc[v] == -1:
                disc[v] = low[v] = timer
                timer += 1
                stack.append((v, u, 0))
            else:
                low[u] = min(low[u], disc[v])
        elif parent != -1:        # u is finished: report to its parent
            low[parent] = min(low[parent], low[u])
            if low[u] > disc[parent]:
                res.append([parent, u])
    return res

print(critical_connections(4, [[0, 1], [1, 2], [2, 0], [1, 3]]))
print(critical_connections(2, [[0, 1]]))
print(critical_connections(3, [[0, 1], [1, 2], [2, 0]]))
print(critical_connections(6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3], [2, 3]]))
print(len(critical_connections(100000, [[i, i + 1] for i in range(99999)])), "bridges")
[[1, 3]]
[[0, 1]]
[]
[[2, 3]]
99999 bridges

Three real bugs

Bug 1: not skipping the parent

Delete if (v == parent) continue;:

[]
[]

Node 3 looks back along its own road, sees node 1 (disc 1), and treats that as a detour: low[3] = 1, not > disc[1]. A road can't be its own detour.

Bug 2: >= instead of >

if (low[v] >= disc[u]):

[[1, 3], [0, 1]]
[[0, 1]]

0 - 1 is reported, but low[1] = 0 equals disc[0] = 0: the detour reaches node 0 itself, so the road is safe. low[v] >= disc[u] is the test for an articulation point (cut vertex), not a bridge.

Bug 3: Kosaraju's second pass on the original graph

for (int v : g.get(u)) … in dfs2:

1
1
3

The first example gives 1 instead of 3: from 0, the original edges lead out to 3 and 4, so the walk swallows other groups.

Complexity

Approach Time Space 1 lakh junctions
SCC: forward + backward BFS from every node O(V · (V + E)) O(V + E) Time Limit Exceeded
Kosaraju O(V + E) O(V + E) 167 ms (big stack)
Bridges: remove each edge + BFS O(E · (V + E)) O(V + E) Time Limit Exceeded
disc / low (Tarjan) O(V + E) O(V + E) 264 ms (big stack)

Common mistakes

Mistake What you see (real) Why Fix
Parent edge not skipped [] (no bridges) a road becomes its own detour if (v == parent) continue
low[v] >= disc[u] an extra bridge [0, 1] that's the cut-vertex test low[v] > disc[u]
Pass 2 on the original graph 1 instead of 3 the walk escapes the group walk the reversed graph
Deep recursion StackOverflowError 1 lakh calls deep big-stack thread or your own stack
Pass 2 in increasing node order wrong groups must follow reverse finish order pop the finish stack
low[u] = min(low[u], low[v]) for a back edge still correct for bridges, but wrong in Tarjan's SCC definitions mixed use disc[v] for back edges
Skipping parent node with parallel edges a real bridge missed or a fake one two roads between the same pair skip the parent edge id

Mini project: print the zones

Kosaraju that prints the members of each SCC (a patrol-zone plan).

import java.util.*;

public class Main {
    // Mini project: Kosaraju printing each zone's junctions.
    static List<List<Integer>> g = new ArrayList<>(), r = new ArrayList<>();
    static boolean[] seen;
    static Deque<Integer> order = new ArrayDeque<>();
    static void dfs1(int u) { seen[u] = true; for (int v : g.get(u)) if (!seen[v]) dfs1(v); order.push(u); }
    static void dfs2(int u, List<Integer> zone) { seen[u] = true; zone.add(u); for (int v : r.get(u)) if (!seen[v]) dfs2(v, zone); }
    public static void main(String[] args) {
        String[] name = {"Clock Tower", "Market", "Station", "Temple", "Fort", "Lake", "College"};
        int[][] streets = {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 3}, {4, 5}, {6, 5}};
        int n = name.length;
        for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); r.add(new ArrayList<>()); }
        for (int[] s : streets) { g.get(s[0]).add(s[1]); r.get(s[1]).add(s[0]); }
        seen = new boolean[n];
        for (int u = 0; u < n; u++) if (!seen[u]) dfs1(u);
        seen = new boolean[n];
        int z = 0;
        while (!order.isEmpty()) {
            int u = order.pop();
            if (seen[u]) continue;
            List<Integer> zone = new ArrayList<>();
            dfs2(u, zone);
            StringBuilder sb = new StringBuilder("zone " + (++z) + ":");
            for (int x : zone) sb.append(" ").append(name[x]);
            System.out.println(sb);
        }
    }
}
zone 1: College
zone 2: Clock Tower Station Market
zone 3: Temple Fort
zone 4: Lake

Practice

1. Articulation points (cut vertices). A non-root u is a cut vertex if some child v has low[v] >= disc[u]; the root is one if it has two or more DFS children.

Solution
import java.util.*;

public class Main {
    // Articulation points: low[v] >= disc[u] for a child v (non-root), or 2+ DFS children (root).
    static List<List<Integer>> adj = new ArrayList<>();
    static int[] disc, low;
    static int timer;
    static TreeSet<Integer> cut = new TreeSet<>();
    static void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        int children = 0;
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                children++;
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (parent != -1 && low[v] >= disc[u]) cut.add(u);
            } else low[u] = Math.min(low[u], disc[v]);
        }
        if (parent == -1 && children > 1) cut.add(u);
    }
    public static void main(String[] args) {
        int n = 5;
        int[][] roads = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}};
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : roads) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        disc = new int[n];
        low = new int[n];
        Arrays.fill(disc, -1);
        dfs(0, -1);
        System.out.println(cut);
    }
}
[1, 3]

Removing junction 1 cuts off 3 and 4; removing 3 cuts off 4.

2. Tarjan's one-pass SCC algorithm. Keep a stack of nodes in the current DFS path; low[u] uses disc[v] only for v still on the stack; when low[u] == disc[u], pop the stack down to u: that's one SCC.

Solution
import sys
sys.setrecursionlimit(10000)

# Tarjan's SCC: one DFS; a node whose low equals its disc is the root of an SCC.
def tarjan_scc(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
    disc, low, on, st, out = [-1] * n, [0] * n, [False] * n, [], []
    timer = [0]
    def dfs(u):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        st.append(u); on[u] = True
        for v in g[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on[v]:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            comp = []
            while True:
                x = st.pop(); on[x] = False; comp.append(x)
                if x == u:
                    break
            out.append(sorted(comp))
    for u in range(n):
        if disc[u] == -1:
            dfs(u)
    return out

print(tarjan_scc(5, [(1, 0), (0, 2), (2, 1), (0, 3), (3, 4)]))
[[4], [3], [0, 1, 2]]

3. Number of Operations to Make Network Connected (LeetCode 1319) and Course Schedule (LeetCode 207): revisit them; in a directed graph, a cycle exists exactly when some SCC has more than one node (or a self-loop).

Quick quiz

Edges: 0→1, 1→2, 2→0, 2→3, 3→4, 4→3. How many SCCs? A) 2 B) 3 C) 1 D) 5

Answer

A) 2. {0, 1, 2} is a loop and {3, 4} is a loop; 2 → 3 goes one way only.

Interview questions

  1. Define an SCC. A largest set of nodes in a directed graph where every node reaches every other.
  2. Why does Kosaraju reverse the graph? The last-finished node lies in a source SCC; reversed, that SCC is a sink, so a DFS from it can't leave it.
  3. Kosaraju vs Tarjan's SCC? Both O(V + E). Kosaraju: two passes and the reversed graph, easier to remember. Tarjan: one pass, a stack, and low-links.
  4. When is an edge a bridge? Tree edge u - v with low[v] > disc[u].
  5. Bridge vs articulation point? Bridge: low[v] > disc[u] (an edge). Articulation point: low[v] >= disc[u] for a non-root, two+ children for the root (a node).
  6. How do you avoid StackOverflowError in Java? Run in a Thread with a large stack size, or write the DFS iteratively.
  7. What is the condensation of a graph? Each SCC shrunk to a node; it's always a DAG, so topological sort (episode 51) applies.

Glossary

Term Meaning
Directed / undirected graph One-way edges / two-way edges
Reachable A path exists following directions
SCC Largest group where everyone reaches everyone
Reversed graph (transpose) Every edge direction flipped
Finish order When DFS finishes each node
Condensation SCCs shrunk to single nodes: a DAG
Source / sink SCC No edges in from / out to other SCCs
Kosaraju Finish order, then DFS on the reversed graph
Stack overflow Recursion too deep for the call stack
Bridge (critical connection) Edge whose removal disconnects the graph
Tree edge / back edge Edge DFS walked down / edge to an earlier node
disc[u] When DFS first reached u
low[u] Smallest disc reachable from u's subtree with one back edge
Articulation point Node whose removal disconnects the graph

Summary

  • SCC: everyone in the group can reach everyone and come back. Searching from every node is O(V · (V + E)).
  • Kosaraju: DFS for finish order, then DFS on the reversed graph in reverse finish order; each walk is one SCC. O(V + E).
  • Deep recursion in Java throws StackOverflowError: use a big-stack thread or your own stack.
  • Bridge: an edge with no detour. One DFS with disc and low: tree edge u - v is a bridge iff low[v] > disc[u].
  • Watch for: not skipping the parent, >= instead of >, and pass 2 on the original graph.
  • Next episode: greedy: activity selection and jump game.