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
utovfollowing 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 reachesu(0, 1, 2, …). - Low-link
low[u]: the smallest discovery time reachable fromu'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
- 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, then0 → 3 → 4) the finish order is1, 2, 4, 3, 0. - 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}. - 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 from0on the reversed graph is trapped inside{0, 1, 2}. - 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)).
The key insight: discovery time and low-link
disc[u]: when DFS first reachesu.low[u]: the smallestdiscthatuor 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 whenlow[v] > disc[u]: nothing undervhas a detour back touor 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
- Define an SCC. A largest set of nodes in a directed graph where every node reaches every other.
- 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.
- 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.
- When is an edge a bridge? Tree edge
u - vwithlow[v] > disc[u]. - 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). - How do you avoid StackOverflowError in Java? Run in a
Threadwith a large stack size, or write the DFS iteratively. - 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
discandlow: tree edgeu - vis a bridge ifflow[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.