Connectivity: Bridges, Articulation Points, SCCs & Condensation
Why this exists
"Is the graph connected?" is a one-line BFS. The questions that matter in practice are sharper. Which single cable, if cut, splits the network? Which router is a single point of failure? Which functions in this program call each other in a cycle, so they must be compiled or analysed together? If I can only add one-way roads, how many do I need so every town can reach every other? Each of these asks about the structure of connectivity, not just its existence, and a brute force answer (delete each edge or vertex, rerun BFS) costs — about operations for a graph with edges. The algorithms in this lesson answer all of them in a single depth-first search, .
The key idea is the low-link value, introduced by Robert Tarjan in his 1972 paper "Depth-first search and linear graph algorithms" (SIAM Journal on Computing 1(2)). Tarjan showed that if you record, for every vertex, the time it was discovered and the earliest-discovered vertex its DFS subtree can "climb back" to, then bridges, articulation points, biconnected components and strongly connected components all fall out as simple comparisons between two integers. S. Rao Kosaraju found a different, two-pass SCC algorithm in the late 1970s (unpublished; Micha Sharir published it independently in 1981), the one sketched in the Graphs overview.
This lesson defines low-link precisely, proves the bridge and articulation-point tests (with the root case and the multi-edge trap), builds 2-edge-connected and biconnected components, derives Tarjan's SCC algorithm, explains why Kosaraju's reverse graph works, and turns SCCs into the condensation DAG so DAG dynamic programming applies to graphs with cycles. All code is iterative.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "critical connection", "necessary road", "edge whose removal disconnects" | Bridges (low-link, ) |
| "critical city / router / server", "single point of failure", "vertex whose removal disconnects" | Articulation points (, root has children) |
| "remains connected after removing any one edge" | 2-edge-connected components (remove bridges) |
| "remains connected after removing any one vertex", "blocks" | Biconnected components with an edge stack, block-cut tree |
| "orient every road so the city stays strongly connected" | Possible iff the graph is connected and has no bridge; orient by DFS |
| Directed graph and "mutually reachable", "kingdoms", "groups that can all reach each other" | SCCs (Tarjan or Kosaraju) |
| "can every city reach every other?" in a directed graph | One SCC? (or BFS from vertex 0 on and on ) |
| Directed graph with cycles and "maximum sum along a path", "collect coins, revisit allowed" | Condensation DAG + DP |
| "minimum number of edges to add so everything is mutually reachable" | of the condensation |
| "minimum number of edges so everything is reachable from vertex 1" | Count condensation sources other than the SCC of vertex 1 |
| Boolean constraints "a or b" on pairs | 2-SAT: SCCs of the implication graph (2-SAT & colouring) |
| up to and a recursive DFS in Python/Java | Iterative low-link DFS |
The meta-trigger: "what happens if this one thing fails?" (undirected) or "who can reach whom, and back?" (directed). Both are low-link questions.
Intuition & first principles
The DFS tree is a skeleton; back edges are the ribs
Run DFS on a connected undirected graph and record the tree edges (the edge you used to discover each new vertex). They form a spanning tree. Every other edge is a back edge that joins a vertex to one of its ancestors in that tree. This is the fundamental fact of undirected DFS: there are no cross edges. If were an edge between two vertices in different branches, the DFS would have discovered from (or from ) while it was exploring, putting them in the same branch. The DFS lesson proves this edge classification; here we exploit it.
A tree edge is fragile: remove it and the tree falls into two pieces. The only things that can glue the pieces back together are back edges that jump from inside the lower piece to above it. So the question "is the tree edge a bridge?" becomes "does any back edge leave the subtree of and land at or higher?" If we knew, for each subtree, the highest point a back edge from it can reach, every bridge question would be one comparison.
Measuring "height" with discovery time
"Higher in the tree" is awkward to compute directly, but the DFS gives a free proxy: the discovery time , the value of a counter incremented each time a vertex is first visited. An ancestor is always discovered before its descendants, so along any root-to-leaf path discovery times strictly increase. "Lands at or higher" becomes "lands at a vertex with ".
The low-link value
Define, for every vertex :
In words: the smallest discovery time reachable from by going down tree edges any number of times and then taking at most one back edge. It is the "highest rib" of the subtree. Two facts make it computable during the same DFS:
- When examines a back edge , is already discovered, so is known: update .
- When a child finishes, its whole subtree has been explored, so is final: update , because the subtree of contains the subtree of .
That is the entire low-link computation. Everything else in this lesson is a different test on the pair .
The precise version of the analogy
"Back edges are ribs" means: in an undirected DFS, every non-tree edge connects a vertex to an ancestor. is the minimum over 's subtree's back-edge endpoints (and itself). All structural tests compare with .
Directed graphs: the same number, a different meaning
In a directed graph DFS also produces forward edges and cross edges (to an already-finished vertex in another branch), so "ribs only go up" fails. Tarjan's SCC algorithm keeps a stack of vertices whose component is undecided and lets low-links use only edges into that stack. A vertex whose low-link equals its own discovery time cannot reach anything older and undecided, so it is the root of its SCC, and the SCC is everything above it on the stack.
Mechanics
Computing tin and low on an undirected graph
Use this graph: a triangle ; an edge ; a triangle ; an edge . Edge indices in input order are , , , , , , , .
flowchart LR
V0(("0")) --- V1(("1"))
V1 --- V2(("2"))
V2 --- V0
V1 ===|"bridge"| V3(("3"))
V3 --- V4(("4"))
V4 --- V5(("5"))
V5 --- V3
V5 ===|"bridge"| V6(("6"))
The thick edges are the bridges; vertices 1, 3 and 5 are the articulation points. The DFS from 0 visits , takes the back edge , returns to 1, goes , takes the back edge , goes , then unwinds. The tree it builds, with back edges dashed and tin/low on every vertex:
flowchart TD
A["0 : tin 0, low 0"] --> B["1 : tin 1, low 0"]
B --> C["2 : tin 2, low 0"]
C -.->|"back"| A
B --> D["3 : tin 3, low 3"]
D --> E["4 : tin 4, low 3"]
E --> F["5 : tin 5, low 3"]
F -.->|"back"| D
F --> G["6 : tin 6, low 6"]
Read the tests off the picture. Tree edge : , nothing in 3's subtree climbs to 1 or above — bridge. Tree edge : — bridge. Tree edge : — not a bridge, the back edge protects it.
Trace: tin and low step by step
Computed by running the iterative algorithm below and logging every event (columns are tin/low for vertices 0–6; - means undiscovered).
| Step | Event | 0 | 1 | 2 | 3 | 4 | 5 | 6 | Verdict |
|---|---|---|---|---|---|---|---|---|---|
| 1 | start at 0 | 0/0 | - | - | - | - | - | - | |
| 2 | tree | 0/0 | 1/1 | - | - | - | - | - | |
| 3 | tree | 0/0 | 1/1 | 2/2 | - | - | - | - | |
| 4 | back | 0/0 | 1/1 | 2/0 | - | - | - | - | |
| 5 | 2 done, return to 1 | 0/0 | 1/0 | 2/0 | - | - | - | - | : not a bridge |
| 6 | tree | 0/0 | 1/0 | 2/0 | 3/3 | - | - | - | |
| 7 | tree | 0/0 | 1/0 | 2/0 | 3/3 | 4/4 | - | - | |
| 8 | tree | 0/0 | 1/0 | 2/0 | 3/3 | 4/4 | 5/5 | - | |
| 9 | back | 0/0 | 1/0 | 2/0 | 3/3 | 4/4 | 5/3 | - | |
| 10 | tree | 0/0 | 1/0 | 2/0 | 3/3 | 4/4 | 5/3 | 6/6 | |
| 11 | 6 done, return to 5 | 0/0 | 1/0 | 2/0 | 3/3 | 4/4 | 5/3 | 6/6 | : bridge (5,6); 5 is a cut vertex |
| 12 | 5 done, return to 4 | 0/0 | 1/0 | 2/0 | 3/3 | 4/3 | 5/3 | 6/6 | : nothing |
| 13 | 4 done, return to 3 | 0/0 | 1/0 | 2/0 | 3/3 | 4/3 | 5/3 | 6/6 | : 3 is a cut vertex, but : not a bridge |
| 14 | 3 done, return to 1 | 0/0 | 1/0 | 2/0 | 3/3 | 4/3 | 5/3 | 6/6 | : bridge (1,3); 1 is a cut vertex |
| 15 | 1 done, return to root 0 | 0/0 | 1/0 | 2/0 | 3/3 | 4/3 | 5/3 | 6/6 | root has 1 child: 0 is not a cut vertex |
Step 13 is the one to stare at: means the subtree of 4 can climb back to 3 but not above it. That is enough to save the edge (there is a second route, ) but not enough to save vertex 3 (every route from 4 to the rest of the graph goes through 3). The difference between and is the difference between edges and vertices.
Bridges
A tree edge , where is 's parent, is a bridge iff
Back edges are never bridges, because a back edge together with the tree path between its endpoints forms a cycle. So the algorithm is: run the low-link DFS, and when a child finishes, compare with .
The multi-edge pitfall
When scans its neighbours it must ignore the tree edge it came in on, otherwise leaks into and no tree edge is ever a bridge. Most textbook code does this with if v == parent: continue. That is wrong when there are parallel edges. If and are joined by two edges, the second one is a genuine back edge — the pair is a 2-cycle, and neither edge is a bridge — but v == parent skips both copies and reports a false bridge. Skip the parent edge by its index, not the parent vertex. CSES "Necessary Roads" and many Codeforces problems contain multi-edges precisely to catch this.
Articulation points
A vertex is an articulation point (cut vertex) if removing it, with its edges, increases the number of connected components. With the same DFS:
- A non-root vertex is an articulation point iff it has a tree child with .
- The root is an articulation point iff it has at least two tree children.
The root needs its own rule because nothing is above it: holds for every child trivially. Parallel edges do not matter here (a back edge to the parent gives , which still satisfies ), but skipping by edge index is harmless and lets one function compute both.
2-edge-connected components
Two vertices are 2-edge-connected if they stay connected after removing any single edge; equivalently, there are two edge-disjoint paths between them. This is an equivalence relation, and its classes are the 2-edge-connected components. They are exactly the connected components of the graph after deleting every bridge. Contract each component to a vertex and the bridges form a forest, the bridge tree (a tree if the original graph was connected). Questions like "how many bridges lie on the path between and ?" become path lengths in the bridge tree, answerable with LCA. For the example graph the components are , and , and the bridge tree is a path of three nodes.
Biconnected components and the edge stack
Vertex connectivity is subtler: two triangles sharing a vertex form a graph with no bridge, yet removing the shared vertex disconnects it. A biconnected component (a block) is a maximal set of edges such that any two of them lie on a common simple cycle; a single bridge is a block on its own. Blocks partition the edges, not the vertices: a cut vertex belongs to every block it touches.
Find them with an edge stack. Push every tree edge and back edge when you first traverse it (push a back edge only from the descendant side, i.e. when , so each edge is pushed once). When child of finishes with , separates 's subtree from the rest, so pop edges down to and including : those edges are one block. In the example the four blocks are the triangle , the bridge , the triangle and the bridge .
The block-cut tree has one node per block and one per cut vertex, with an edge between a cut vertex and every block containing it. It is always a tree (a forest for a disconnected graph), and it turns "does every path from to pass through ?" into a tree path question. It is the vertex analogue of the bridge tree.
Strongly connected components: Tarjan's algorithm
In a directed graph, and are strongly connected if each can reach the other. That is an equivalence relation, and its classes are the strongly connected components (SCCs). Tarjan's algorithm finds them in one DFS:
- Maintain a global stack of vertices and an
on_stackflag. Push each vertex when it is discovered. - For a tree edge : recurse, then .
- For a non-tree edge with on the stack: .
- For a non-tree edge to a vertex not on the stack: ignore it. That vertex belongs to an SCC that is already complete.
- When finishes, if , is the root of an SCC: pop the stack down to and including ; the popped vertices are the SCC.
Run it on this 8-vertex graph. The SCCs are , , and .
flowchart LR
V0(("0")) --> V1(("1"))
V1 --> V2(("2"))
V2 --> V0
V1 --> V3(("3"))
V3 --> V4(("4"))
V4 --> V5(("5"))
V5 --> V3
V2 --> V6(("6"))
V6 --> V5
V6 --> V7(("7"))
V4 --> V7
Trace: Tarjan's algorithm
Generated by scripts/traces/tarjan_scc.py (the same run the visualizer plays). Adjacency lists are scanned in input order.
| Step | Event | Stack after | Low-link change | SCC emitted |
|---|---|---|---|---|
| 1 | start at 0, tin 0 | 0 | ||
| 2 | tree , tin 1 | 0 1 | ||
| 3 | tree , tin 2 | 0 1 2 | ||
| 4 | , 0 on stack | 0 1 2 | ||
| 5 | tree , tin 3 | 0 1 2 6 | ||
| 6 | tree , tin 4 | 0 1 2 6 5 | ||
| 7 | tree , tin 5 | 0 1 2 6 5 3 | ||
| 8 | tree , tin 6 | 0 1 2 6 5 3 4 | ||
| 9 | , 5 on stack | 0 1 2 6 5 3 4 | ||
| 10 | tree , tin 7 | 0 1 2 6 5 3 4 7 | ||
| 11 | 7 finishes, | 0 1 2 6 5 3 4 | {7} | |
| 12 | 4 finishes, | unchanged | ||
| 13 | back in 3 | unchanged | ||
| 14 | 3 finishes, | unchanged | ||
| 15 | 5 finishes, | 0 1 2 6 | {3, 4, 5} | |
| 16 | , 7 not on stack | 0 1 2 6 | ignored | |
| 17 | 6 finishes, | 0 1 2 | {6} | |
| 18 | 2 finishes, | 0 1 2 | ||
| 19 | back in 1 | 0 1 2 | ||
| 20 | , 3 not on stack | 0 1 2 | ignored | |
| 21 | 1 finishes, | 0 1 2 | ||
| 22 | 0 finishes, | empty | {0, 1, 2} |
The SCCs come out as , a reverse topological order of the condensation: every edge between components goes from a later-emitted SCC to an earlier one. Steps 16 and 20 show the on-stack check at work: and point into finished components and must not lower low-links, or a finished component with a smaller could wrongly merge into the current one.
Kosaraju's algorithm: two passes
Kosaraju's algorithm, the one in the overview, uses two plain DFS passes and no low-links:
- DFS the whole graph , appending each vertex to a list when it finishes.
- Build the reverse graph (every edge flipped).
- Go through vertices in decreasing finish time. Each still-unassigned vertex starts a DFS in ; everything that DFS reaches (and is unassigned) is one SCC.
On the 8-vertex graph the finish order of pass 1 is , so pass 2 starts at 0 and finds , then 6 gives , then 5 gives , then 7 gives . Kosaraju emits SCCs in topological order — the opposite of Tarjan. Why reversing the graph works is proved in the correctness section.
flowchart LR
P1["Pass 1: DFS on G, record finish order"] --> R["Reverse all edges: G^R"]
R --> P2["Pass 2: DFS on G^R in decreasing finish time"]
P2 --> OUT["Each pass-2 tree = one SCC, in topological order"]
The condensation DAG
Contract every SCC to a single vertex and keep one edge whenever some edge goes from a vertex in to a vertex in . The result, the condensation (or component graph) , is always a DAG: if it had a cycle , every vertex of every could reach every other, so they would be one SCC. For our graph:
flowchart LR
A["A = {0,1,2}, coins 6"] --> B["B = {3,4,5}, coins 15"]
A --> C["C = {6}, coins 7"]
C --> B
C --> D["D = {7}, coins 8"]
B --> D
This is where SCCs pay off. Any question that is easy on a DAG — longest path, number of paths, reachability counts — becomes solvable on a graph with cycles, as long as the quantity behaves sensibly inside a component. In CSES Coin Collector, each room holds coins, you may walk along directed tunnels and revisit rooms, and you want the maximum total collected. Inside an SCC you can visit every room and come back, so you collect the whole component's coins. Across components you can only move forward in the DAG. So:
and the answer is . Process components so successors are done first, which is exactly Tarjan's emission order. With coins on the 8-vertex graph: , , , , achieved by .
Making a digraph strongly connected with the fewest edges
Let the condensation have components, sources (in-degree 0) and sinks (out-degree 0); an isolated component counts as both. If the answer is 0. Otherwise it is
The lower bound is immediate: every source needs at least one new incoming edge and every sink at least one new outgoing edge, and one new edge supplies one of each. That edges always suffice was proved by Eswaran and Tarjan ("Augmentation problems", SIAM Journal on Computing 5(4), 1976); the construction pairs sinks with sources along a carefully chosen matching and closes the rest into a cycle. For the 8-vertex graph: one source (), one sink (), so one edge suffices — add . A brute-force check over all small graphs (up to 5 vertices) agrees with the formula; it is in the verification script I used for this page.
The ladder: brute force → better → optimal
The problem: find all bridges (or articulation points) of an undirected graph, and all SCCs of a directed graph.
Rung 1: delete and recount —
For each edge, remove it, count components with BFS or union-find, and compare with the original count; for articulation points do the same per vertex, . For SCCs, BFS from every vertex and group vertices with : time, memory. I tested every faster version on this page against these on thousands of random small graphs. At they are operations.
Rung 2: cover tree paths with union-find —
Build any spanning tree; for each non-tree edge , mark every tree edge on the tree path from to as "covered" (it lies on a cycle). Uncovered tree edges are bridges. Naively each path costs ; with union-find that skips already-covered edges the total is near-linear. It does not extend cleanly to articulation points or SCCs.
Rung 3: one low-link DFS —
Tarjan's low-link DFS computes all bridges and articulation points in one pass, and Tarjan's SCC algorithm (or Kosaraju's two passes) computes all SCCs in linear time. Nothing can beat this asymptotically: any correct algorithm must look at every edge, since a single unseen edge can turn a bridge into a non-bridge.
Rung 4: the same thing without recursion
Asymptotically identical, practically decisive. A recursive DFS on a path of vertices needs stack frames: Python's default recursion limit is 1000, Java's default thread stack overflows long before that, and even C++ can overflow Windows' 1 MB default stack. The iterative versions keep an explicit vertex stack plus a per-vertex "next neighbour index", which reproduces the recursive order exactly.
| Rung | Bridges / cut vertices | SCCs | Memory | Notes |
|---|---|---|---|---|
| 1. Delete and recount | / | for SCC matrix | Reference answer for testing | |
| 2. Cover tree paths | bridges only | n/a | Needs spanning tree + DSU | |
| 3. Low-link DFS (recursive) | call stack | Crashes on deep graphs in Python/Java | ||
| 4. Low-link DFS (iterative) | explicit stack | What to submit |
Correctness
Why there are no cross edges in an undirected DFS
Suppose is an edge and is discovered first. While is active (on the DFS stack), the DFS explores all of 's neighbours before finishes, so is discovered before finishes — inside 's subtree. Hence is a descendant of : every edge joins an ancestor–descendant pair. Non-tree edges are therefore back edges.
The low-link recurrence computes the definition
By induction on finishing order. When finishes, every child has finished and (inductive hypothesis) equals the minimum over back-edge endpoints from 's subtree, or . The subtree of is plus its children's subtrees, so the minimum over it is — exactly what the algorithm took. One subtlety: the update for a "back edge" from also fires for edges where is a descendant that was already visited (the same edge seen from the top). Then and the update changes nothing, so the formula is unaffected.
Bridge test
Claim. A tree edge is a bridge iff .
If : no back edge from the subtree of reaches or any ancestor of . Since there are no cross edges, the only edges leaving the subtree of are back edges to proper ancestors of — which are and 's ancestors, all with — and the tree edge itself. With none of the former exist, so removing cuts the subtree off. Bridge.
If : some back edge has in the subtree of and , so is or an ancestor of . Here "back edge" must not be the edge itself, which is why we skip the entering edge by index. The cycle (tree path down, back edge up) contains , and an edge on a cycle is never a bridge. ∎
Parallel edges fit this proof without change if — and only if — the second copy of is treated as a back edge, which index-skipping does and vertex-skipping does not.
Articulation point test
Claim (non-root). A non-root vertex is an articulation point iff some tree child has .
If such exists: the edges leaving 's subtree are the tree edge and back edges to proper ancestors of , i.e. to or above. says none goes above , so all of them land on . Removing separates the subtree from 's parent, which exists because is not the root. Cut vertex.
If every child has : each child subtree has a back edge to a proper ancestor of , so after deleting each child subtree is still connected to 's parent, and so is everything else (the part of the graph outside 's subtree is connected through the tree minus 's subtree). Not a cut vertex. ∎
Claim (root). The root is an articulation point iff it has at least two tree children.
With no cross edges, there is no edge between two different child subtrees of the root. If there are at least two, deleting the root leaves them disconnected. If there is exactly one, deleting the root leaves that subtree, which is connected through its tree edges. ∎
The general rule fails at the root because is the global minimum: always holds, so a leaf root with one child would be wrongly reported.
Biconnected components via the edge stack
When child of finishes with , every edge pushed since lies inside 's subtree or joins it to (no back edge escapes above ). Blocks nested deeper inside the subtree were already popped when their own separating vertex was detected, because a deeper vertex finishes first. So the remaining edges above form exactly one block, separated from the rest by . A full proof is in Tarjan's 1972 paper and in Hopcroft & Tarjan, "Efficient algorithms for graph manipulation", CACM 16(6), 1973.
Tarjan's SCC algorithm
Call the first vertex of an SCC to be discovered its root. Three facts:
-
An SCC is a contiguous subtree in the DFS forest, hanging from its root. All vertices of the SCC are reachable from the root, and when the root is discovered none of them is visited (the root is first), so the white-path theorem puts them all in the root's subtree. Vertices on the tree path between the root and one of them are in the SCC too (they reach that vertex, which reaches the root, which reaches them).
-
Invariant: the stack contains exactly the discovered vertices whose SCC root has not yet finished, in discovery order. A vertex is pushed at discovery and popped only when its root is processed.
-
iff is a root. If is not a root, the root of its SCC is a proper ancestor, still on the stack. Some path inside the SCC goes from 's subtree back to ; its first edge leaving the subtree goes to a vertex in the same SCC, which is on the stack and discovered earlier than , so . Conversely, if is a root, any edge out of 's subtree to an on-stack vertex with would mean reaches ; being on the stack means 's root is still active, so it is an ancestor of — and reaches it and it reaches , putting in 's SCC, contradicting that is a root. So cannot drop below .
Edges to vertices not on the stack point into SCCs that are already complete; the target cannot reach (otherwise it would be in 's SCC and still on the stack), so they are irrelevant and must be ignored. When is a root and finishes, the vertices above it on the stack are its descendants not yet assigned to a deeper SCC — by fact 1, exactly its SCC. ∎
Using instead of for an on-stack non-tree edge also produces correct SCCs (the value is still exactly when it should be), but it changes the meaning of and is not valid for the articulation-point test (a random test against brute force finds counterexamples within a few thousand small graphs; the bridge test happens to survive). Use everywhere and you never have to remember which variant is safe where.
Why Kosaraju's reverse graph works
Let be the largest finish time of any vertex in SCC after pass 1.
Lemma. If the condensation has an edge , then .
Proof. Let be the first vertex of discovered. If : at that moment everything in and is unvisited and reachable from (through the edge ), so all of it becomes a descendant of and finishes before . Hence . If : cannot reach (otherwise they would be one SCC), so the DFS from finishes all of without touching ; is discovered later and finishes later. Hence . ∎
So the vertex with the largest finish time lies in a source SCC of the condensation. In every edge flips, so that SCC becomes a sink: a DFS from it in reaches its own SCC and nothing else. Remove that SCC; the vertex with the next-largest finish time among the rest is in a source of what remains (by the lemma applied to the remaining components), hence a sink of the remaining reversed graph, and the argument repeats. By induction every pass-2 DFS tree is exactly one SCC, and they appear in topological order of the condensation. ∎
Coin collector DP
Within an SCC every vertex can reach every other and return, so any walk that enters the SCC can collect all its coins before leaving by any edge out of it; no walk can re-enter an SCC after leaving it (that would create a cycle in the condensation). So every walk corresponds to a path in the condensation and collects at most the sum of the components on it, and every condensation path is achievable. The maximum over paths in a DAG is the standard DP, correct when components are processed after all their successors.
Complexity
| Algorithm | Time | Extra space | Notes |
|---|---|---|---|
| Bridges + articulation points | (adjacency) + | Each edge examined twice (once per endpoint) | |
| 2-edge-connected components | One more traversal skipping bridges | ||
| Biconnected components (edge stack) | edge stack | Each edge pushed and popped once | |
| Tarjan SCC | One DFS; each vertex pushed and popped once | ||
| Kosaraju SCC | for | Two DFS passes; touches every edge twice plus building | |
| Condensation + DAG DP | Duplicated condensation edges are harmless for max DP | ||
| Minimum edges to strongly connect (count) | Count sources and sinks |
Best, average and worst case are the same: every vertex and edge is touched a constant number of times regardless of structure. There is no amortisation.
Constants matter for -edge graphs. Tarjan beats Kosaraju in practice because it makes one pass and never builds the reverse graph — roughly half the memory traffic. Both are dominated by cache misses on adjacency lists; a flat compressed-sparse-row (CSR) layout (one int[] of neighbours plus an offsets array, as in the Java version below) is usually noticeably faster than lists of boxed lists, because consecutive neighbours share cache lines. In CPython expect on the order of a second for vertices and edges, so read input in bulk.
Implementation
Bridges and articulation points (iterative, multi-edge safe)
Edges are given as a list of pairs; the function returns the indices of bridge edges and the list of cut vertices, both sorted. All four versions run the same tests: the 7-vertex example (bridges are edges 3 and 7, cut vertices 1, 3, 5), a doubled edge (no bridge), a single edge (one bridge), and a star (every edge a bridge, the centre a cut vertex).
def bridges_and_cut_vertices(n: int, edges: list[tuple[int, int]]) -> tuple[list[int], list[int]]:
"""Iterative low-link DFS. Skips the entering edge by index, so parallel edges are handled."""
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for i, (u, v) in enumerate(edges):
adj[u].append((v, i))
adj[v].append((u, i))
tin = [-1] * n
low = [0] * n
parent_edge = [-1] * n
it = [0] * n # next neighbour index to scan, per vertex
is_bridge = [False] * len(edges)
is_cut = [False] * n
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
root_children = 0
stack = [root]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v, eid = adj[u][it[u]]
it[u] += 1
if eid == parent_edge[u]:
continue # the tree edge we came in on
if tin[v] == -1: # tree edge: descend
tin[v] = low[v] = timer
timer += 1
parent_edge[v] = eid
stack.append(v)
else: # back edge (or the same edge seen from above)
low[u] = min(low[u], tin[v])
else: # u is finished: report to its parent
stack.pop()
if not stack:
break
p = stack[-1]
low[p] = min(low[p], low[u])
if low[u] > tin[p]:
is_bridge[parent_edge[u]] = True
if p == root:
root_children += 1
elif low[u] >= tin[p]:
is_cut[p] = True
if root_children >= 2:
is_cut[root] = True
return ([i for i in range(len(edges)) if is_bridge[i]],
[v for v in range(n) if is_cut[v]])
if __name__ == "__main__":
example = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (5, 6)]
assert bridges_and_cut_vertices(7, example) == ([3, 7], [1, 3, 5])
assert bridges_and_cut_vertices(2, [(0, 1), (0, 1)]) == ([], []) # parallel edges: no bridge
assert bridges_and_cut_vertices(2, [(0, 1)]) == ([0], [])
assert bridges_and_cut_vertices(4, [(0, 1), (0, 2), (0, 3)]) == ([0, 1, 2], [0])
print("bridges and cut vertices: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BridgesCutVertices {
/** Returns {bridge edge indices, cut vertices}, both sorted. */
static List<List<Integer>> solve(int n, int[][] edges) {
int m = edges.length;
int[] deg = new int[n];
for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
int[] start = new int[n + 1];
for (int i = 0; i < n; i++) start[i + 1] = start[i] + deg[i];
int[] to = new int[2 * m], id = new int[2 * m], fill = Arrays.copyOf(start, n);
for (int i = 0; i < m; i++) {
int u = edges[i][0], v = edges[i][1];
to[fill[u]] = v; id[fill[u]++] = i;
to[fill[v]] = u; id[fill[v]++] = i;
}
int[] tin = new int[n], low = new int[n], parentEdge = new int[n], it = new int[n];
Arrays.fill(tin, -1);
Arrays.fill(parentEdge, -1);
for (int i = 0; i < n; i++) it[i] = start[i];
boolean[] isBridge = new boolean[m], isCut = new boolean[n];
int[] stack = new int[n];
int timer = 0;
for (int root = 0; root < n; root++) {
if (tin[root] != -1) continue;
tin[root] = low[root] = timer++;
int rootChildren = 0, top = 0;
stack[top++] = root;
while (top > 0) {
int u = stack[top - 1];
if (it[u] < start[u + 1]) {
int v = to[it[u]], eid = id[it[u]];
it[u]++;
if (eid == parentEdge[u]) continue;
if (tin[v] == -1) {
tin[v] = low[v] = timer++;
parentEdge[v] = eid;
stack[top++] = v;
} else {
low[u] = Math.min(low[u], tin[v]);
}
} else {
top--;
if (top == 0) break;
int p = stack[top - 1];
low[p] = Math.min(low[p], low[u]);
if (low[u] > tin[p]) isBridge[parentEdge[u]] = true;
if (p == root) rootChildren++;
else if (low[u] >= tin[p]) isCut[p] = true;
}
}
if (rootChildren >= 2) isCut[root] = true;
}
List<Integer> bridges = new ArrayList<>(), cuts = new ArrayList<>();
for (int i = 0; i < m; i++) if (isBridge[i]) bridges.add(i);
for (int v = 0; v < n; v++) if (isCut[v]) cuts.add(v);
return List.of(bridges, cuts);
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[][] example = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {5, 6}};
check(solve(7, example).equals(List.of(List.of(3, 7), List.of(1, 3, 5))), "example");
check(solve(2, new int[][]{{0, 1}, {0, 1}}).equals(List.of(List.of(), List.of())), "parallel");
check(solve(2, new int[][]{{0, 1}}).equals(List.of(List.of(0), List.of())), "single edge");
check(solve(4, new int[][]{{0, 1}, {0, 2}, {0, 3}}).equals(List.of(List.of(0, 1, 2), List.of(0))), "star");
System.out.println("bridges and cut vertices: all tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
// Returns {bridge edge indices, cut vertices}, both sorted.
std::pair<std::vector<int>, std::vector<int>>
bridgesAndCutVertices(int n, const std::vector<std::pair<int, int>>& edges) {
int m = static_cast<int>(edges.size());
std::vector<std::vector<std::pair<int, int>>> adj(n); // (neighbour, edge id)
for (int i = 0; i < m; ++i) {
adj[edges[i].first].push_back({edges[i].second, i});
adj[edges[i].second].push_back({edges[i].first, i});
}
std::vector<int> tin(n, -1), low(n, 0), parentEdge(n, -1), it(n, 0);
std::vector<char> isBridge(m, 0), isCut(n, 0);
int timer = 0;
for (int root = 0; root < n; ++root) {
if (tin[root] != -1) continue;
tin[root] = low[root] = timer++;
int rootChildren = 0;
std::vector<int> stack{root};
while (!stack.empty()) {
int u = stack.back();
if (it[u] < static_cast<int>(adj[u].size())) {
auto [v, eid] = adj[u][it[u]++];
if (eid == parentEdge[u]) continue;
if (tin[v] == -1) {
tin[v] = low[v] = timer++;
parentEdge[v] = eid;
stack.push_back(v);
} else {
low[u] = std::min(low[u], tin[v]);
}
} else {
stack.pop_back();
if (stack.empty()) break;
int p = stack.back();
low[p] = std::min(low[p], low[u]);
if (low[u] > tin[p]) isBridge[parentEdge[u]] = 1;
if (p == root) ++rootChildren;
else if (low[u] >= tin[p]) isCut[p] = 1;
}
}
if (rootChildren >= 2) isCut[root] = 1;
}
std::vector<int> bridges, cuts;
for (int i = 0; i < m; ++i) if (isBridge[i]) bridges.push_back(i);
for (int v = 0; v < n; ++v) if (isCut[v]) cuts.push_back(v);
return {bridges, cuts};
}
int main() {
using V = std::vector<int>;
auto r1 = bridgesAndCutVertices(7, {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {5, 6}});
assert(r1.first == (V{3, 7}) && r1.second == (V{1, 3, 5}));
auto r2 = bridgesAndCutVertices(2, {{0, 1}, {0, 1}});
assert(r2.first.empty() && r2.second.empty());
auto r3 = bridgesAndCutVertices(2, {{0, 1}});
assert(r3.first == (V{0}) && r3.second.empty());
auto r4 = bridgesAndCutVertices(4, {{0, 1}, {0, 2}, {0, 3}});
assert(r4.first == (V{0, 1, 2}) && r4.second == (V{0}));
std::cout << "bridges and cut vertices: all tests passed\n";
}
function bridgesAndCutVertices(n: number, edges: [number, number][]): [number[], number[]] {
const adj: [number, number][][] = Array.from({ length: n }, () => []);
edges.forEach(([u, v], i) => {
adj[u].push([v, i]);
adj[v].push([u, i]);
});
const tin = new Array<number>(n).fill(-1);
const low = new Array<number>(n).fill(0);
const parentEdge = new Array<number>(n).fill(-1);
const it = new Array<number>(n).fill(0);
const isBridge = new Array<boolean>(edges.length).fill(false);
const isCut = new Array<boolean>(n).fill(false);
let timer = 0;
for (let root = 0; root < n; root++) {
if (tin[root] !== -1) continue;
tin[root] = low[root] = timer++;
let rootChildren = 0;
const stack: number[] = [root];
while (stack.length > 0) {
const u = stack[stack.length - 1];
if (it[u] < adj[u].length) {
const [v, eid] = adj[u][it[u]++];
if (eid === parentEdge[u]) continue;
if (tin[v] === -1) {
tin[v] = low[v] = timer++;
parentEdge[v] = eid;
stack.push(v);
} else {
low[u] = Math.min(low[u], tin[v]);
}
} else {
stack.pop();
if (stack.length === 0) break;
const p = stack[stack.length - 1];
low[p] = Math.min(low[p], low[u]);
if (low[u] > tin[p]) isBridge[parentEdge[u]] = true;
if (p === root) rootChildren++;
else if (low[u] >= tin[p]) isCut[p] = true;
}
}
if (rootChildren >= 2) isCut[root] = true;
}
const bridges: number[] = [];
const cuts: number[] = [];
isBridge.forEach((b, i) => { if (b) bridges.push(i); });
isCut.forEach((c, v) => { if (c) cuts.push(v); });
return [bridges, cuts];
}
function same(a: unknown, b: unknown): boolean {
return JSON.stringify(a) === JSON.stringify(b);
}
const example: [number, number][] = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3], [5, 6]];
if (!same(bridgesAndCutVertices(7, example), [[3, 7], [1, 3, 5]])) throw new Error("example");
if (!same(bridgesAndCutVertices(2, [[0, 1], [0, 1]]), [[], []])) throw new Error("parallel");
if (!same(bridgesAndCutVertices(2, [[0, 1]]), [[0], []])) throw new Error("single edge");
if (!same(bridgesAndCutVertices(4, [[0, 1], [0, 2], [0, 3]]), [[0, 1, 2], [0]])) throw new Error("star");
console.log("bridges and cut vertices: all tests passed");
Tarjan's SCC algorithm (iterative)
Returns the SCCs in the order Tarjan emits them (reverse topological order of the condensation), each sorted. Tests: the 8-vertex example gives [[7], [3, 4, 5], [6], [0, 1, 2]], a chain gives [[2], [1], [0]], and a single vertex with a self-loop is one SCC.
def tarjan_scc(n: int, adj: list[list[int]]) -> list[list[int]]:
"""SCCs in reverse topological order of the condensation (sinks first)."""
tin = [-1] * n
low = [0] * n
on_stack = [False] * n
it = [0] * n
stack: list[int] = [] # Tarjan's stack: vertices whose SCC is undecided
comps: list[list[int]] = []
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
stack.append(root)
on_stack[root] = True
call = [root] # explicit DFS call stack
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]
it[u] += 1
if tin[v] == -1:
tin[v] = low[v] = timer
timer += 1
stack.append(v)
on_stack[v] = True
call.append(v)
elif on_stack[v]:
low[u] = min(low[u], tin[v])
else:
call.pop()
if call:
p = call[-1]
low[p] = min(low[p], low[u])
if low[u] == tin[u]: # u is the root of an SCC
comp = []
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u:
break
comps.append(sorted(comp))
return comps
if __name__ == "__main__":
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (2, 6), (6, 5), (6, 7), (4, 7)]
adj = [[] for _ in range(8)]
for u, v in edges:
adj[u].append(v)
assert tarjan_scc(8, adj) == [[7], [3, 4, 5], [6], [0, 1, 2]]
assert tarjan_scc(3, [[1], [2], []]) == [[2], [1], [0]]
assert tarjan_scc(1, [[0]]) == [[0]]
print("tarjan scc: all tests passed")
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TarjanScc {
static List<List<Integer>> scc(int n, List<List<Integer>> adj) {
int[] tin = new int[n], low = new int[n], it = new int[n];
java.util.Arrays.fill(tin, -1);
boolean[] onStack = new boolean[n];
int[] stack = new int[n], call = new int[n];
int top = 0, timer = 0;
List<List<Integer>> comps = new ArrayList<>();
for (int root = 0; root < n; root++) {
if (tin[root] != -1) continue;
tin[root] = low[root] = timer++;
stack[top++] = root;
onStack[root] = true;
int ctop = 0;
call[ctop++] = root;
while (ctop > 0) {
int u = call[ctop - 1];
if (it[u] < adj.get(u).size()) {
int v = adj.get(u).get(it[u]++);
if (tin[v] == -1) {
tin[v] = low[v] = timer++;
stack[top++] = v;
onStack[v] = true;
call[ctop++] = v;
} else if (onStack[v]) {
low[u] = Math.min(low[u], tin[v]);
}
} else {
ctop--;
if (ctop > 0) {
int p = call[ctop - 1];
low[p] = Math.min(low[p], low[u]);
}
if (low[u] == tin[u]) {
List<Integer> comp = new ArrayList<>();
while (true) {
int w = stack[--top];
onStack[w] = false;
comp.add(w);
if (w == u) break;
}
Collections.sort(comp);
comps.add(comp);
}
}
}
}
return comps;
}
static List<List<Integer>> build(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(e[1]);
return adj;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[][] edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {2, 6}, {6, 5}, {6, 7}, {4, 7}};
check(scc(8, build(8, edges)).equals(List.of(List.of(7), List.of(3, 4, 5), List.of(6), List.of(0, 1, 2))), "example");
check(scc(3, build(3, new int[][]{{0, 1}, {1, 2}})).equals(List.of(List.of(2), List.of(1), List.of(0))), "chain");
check(scc(1, build(1, new int[][]{{0, 0}})).equals(List.of(List.of(0))), "self-loop");
System.out.println("tarjan scc: all tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> tarjanScc(int n, const std::vector<std::vector<int>>& adj) {
std::vector<int> tin(n, -1), low(n, 0), it(n, 0), stack, call;
std::vector<char> onStack(n, 0);
std::vector<std::vector<int>> comps;
int timer = 0;
for (int root = 0; root < n; ++root) {
if (tin[root] != -1) continue;
tin[root] = low[root] = timer++;
stack.push_back(root);
onStack[root] = 1;
call.push_back(root);
while (!call.empty()) {
int u = call.back();
if (it[u] < static_cast<int>(adj[u].size())) {
int v = adj[u][it[u]++];
if (tin[v] == -1) {
tin[v] = low[v] = timer++;
stack.push_back(v);
onStack[v] = 1;
call.push_back(v);
} else if (onStack[v]) {
low[u] = std::min(low[u], tin[v]);
}
} else {
call.pop_back();
if (!call.empty()) low[call.back()] = std::min(low[call.back()], low[u]);
if (low[u] == tin[u]) {
std::vector<int> comp;
while (true) {
int w = stack.back();
stack.pop_back();
onStack[w] = 0;
comp.push_back(w);
if (w == u) break;
}
std::sort(comp.begin(), comp.end());
comps.push_back(comp);
}
}
}
}
return comps;
}
int main() {
std::vector<std::vector<int>> adj(8);
int edges[][2] = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {2, 6}, {6, 5}, {6, 7}, {4, 7}};
for (auto& e : edges) adj[e[0]].push_back(e[1]);
using VV = std::vector<std::vector<int>>;
assert(tarjanScc(8, adj) == (VV{{7}, {3, 4, 5}, {6}, {0, 1, 2}}));
assert(tarjanScc(3, {{1}, {2}, {}}) == (VV{{2}, {1}, {0}}));
assert(tarjanScc(1, {{0}}) == (VV{{0}}));
std::cout << "tarjan scc: all tests passed\n";
}
function tarjanScc(n: number, adj: number[][]): number[][] {
const tin = new Array<number>(n).fill(-1);
const low = new Array<number>(n).fill(0);
const it = new Array<number>(n).fill(0);
const onStack = new Array<boolean>(n).fill(false);
const stack: number[] = [];
const comps: number[][] = [];
let timer = 0;
for (let root = 0; root < n; root++) {
if (tin[root] !== -1) continue;
tin[root] = low[root] = timer++;
stack.push(root);
onStack[root] = true;
const call: number[] = [root];
while (call.length > 0) {
const u = call[call.length - 1];
if (it[u] < adj[u].length) {
const v = adj[u][it[u]++];
if (tin[v] === -1) {
tin[v] = low[v] = timer++;
stack.push(v);
onStack[v] = true;
call.push(v);
} else if (onStack[v]) {
low[u] = Math.min(low[u], tin[v]);
}
} else {
call.pop();
if (call.length > 0) {
const p = call[call.length - 1];
low[p] = Math.min(low[p], low[u]);
}
if (low[u] === tin[u]) {
const comp: number[] = [];
while (true) {
const w = stack.pop() as number;
onStack[w] = false;
comp.push(w);
if (w === u) break;
}
comps.push(comp.sort((a, b) => a - b));
}
}
}
}
return comps;
}
const sccEdges: [number, number][] = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3], [2, 6], [6, 5], [6, 7], [4, 7]];
const sccAdj: number[][] = Array.from({ length: 8 }, () => []);
for (const [u, v] of sccEdges) sccAdj[u].push(v);
const eq = (a: unknown, b: unknown) => JSON.stringify(a) === JSON.stringify(b);
if (!eq(tarjanScc(8, sccAdj), [[7], [3, 4, 5], [6], [0, 1, 2]])) throw new Error("example");
if (!eq(tarjanScc(3, [[1], [2], []]), [[2], [1], [0]])) throw new Error("chain");
if (!eq(tarjanScc(1, [[0]]), [[0]])) throw new Error("self-loop");
console.log("tarjan scc: all tests passed");
Variant: Kosaraju, iteratively
The overview's Kosaraju is recursive; this version uses an explicit stack in pass 1 (where finish order matters) and a plain stack in pass 2 (where only reachability matters, so any traversal order works).
def kosaraju_scc(n: int, adj: list[list[int]]) -> list[list[int]]:
"""SCCs in topological order of the condensation (sources first)."""
seen = [False] * n
order: list[int] = [] # vertices by increasing finish time
it = [0] * n
for s in range(n):
if seen[s]:
continue
seen[s] = True
stack = [s]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]
it[u] += 1
if not seen[v]:
seen[v] = True
stack.append(v)
else:
stack.pop()
order.append(u)
radj: list[list[int]] = [[] for _ in range(n)]
for u in range(n):
for v in adj[u]:
radj[v].append(u)
comp = [-1] * n
comps: list[list[int]] = []
for s in reversed(order): # decreasing finish time
if comp[s] != -1:
continue
comp[s] = len(comps)
members, stack = [s], [s]
while stack:
u = stack.pop()
for v in radj[u]:
if comp[v] == -1:
comp[v] = len(comps)
members.append(v)
stack.append(v)
comps.append(sorted(members))
return comps
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (2, 6), (6, 5), (6, 7), (4, 7)]
adj = [[] for _ in range(8)]
for u, v in edges:
adj[u].append(v)
assert kosaraju_scc(8, adj) == [[0, 1, 2], [6], [3, 4, 5], [7]] # topological order
print("kosaraju: ok")
Variant: biconnected components with an edge stack
def biconnected_components(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
"""Blocks as sorted lists of edge indices. Iterative; parallel edges handled by edge id."""
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for i, (u, v) in enumerate(edges):
if u != v: # a self-loop belongs to no block
adj[u].append((v, i))
adj[v].append((u, i))
tin, low, pe, it = [-1] * n, [0] * n, [-1] * n, [0] * n
estack: list[int] = []
blocks: list[list[int]] = []
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
stack = [root]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v, eid = adj[u][it[u]]
it[u] += 1
if eid == pe[u]:
continue
if tin[v] == -1:
tin[v] = low[v] = timer
timer += 1
pe[v] = eid
estack.append(eid)
stack.append(v)
elif tin[v] < tin[u]: # back edge, pushed from the lower end only
low[u] = min(low[u], tin[v])
estack.append(eid)
else:
stack.pop()
if not stack:
break
p = stack[-1]
low[p] = min(low[p], low[u])
if low[u] >= tin[p]: # p separates u's subtree: pop one block
block = []
while True:
e = estack.pop()
block.append(e)
if e == pe[u]:
break
blocks.append(sorted(block))
return sorted(blocks)
example = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (5, 6)]
assert biconnected_components(7, example) == [[0, 1, 2], [3], [4, 5, 6], [7]]
bowtie = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)] # two triangles sharing vertex 2
assert biconnected_components(5, bowtie) == [[0, 1, 2], [3, 4, 5]]
print("biconnected components: ok")
Variant: 2-edge-connected components and the bridge tree
def two_edge_connected(n: int, edges: list[tuple[int, int]], bridge_ids: list[int]) -> list[int]:
"""Component label per vertex after deleting the given bridges."""
is_bridge = set(bridge_ids)
adj: list[list[int]] = [[] for _ in range(n)]
for i, (u, v) in enumerate(edges):
if i not in is_bridge:
adj[u].append(v)
adj[v].append(u)
comp = [-1] * n
c = 0
for s in range(n):
if comp[s] != -1:
continue
comp[s] = c
stack = [s]
while stack:
u = stack.pop()
for v in adj[u]:
if comp[v] == -1:
comp[v] = c
stack.append(v)
c += 1
return comp
example = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (5, 6)]
labels = two_edge_connected(7, example, [3, 7]) # bridges found by the code above
assert labels == [0, 0, 0, 1, 1, 1, 2]
bridge_tree = sorted({tuple(sorted((labels[example[b][0]], labels[example[b][1]]))) for b in [3, 7]})
assert bridge_tree == [(0, 1), (1, 2)] # a path of three components
print("2-edge-connected components: ok")
Variant: condensation and DP on it
This reuses Tarjan's emission order, so successors are always processed before predecessors.
def max_coins(n: int, adj: list[list[int]], coins: list[int]) -> int:
# SCC labels via an iterative Tarjan (same as above, labelling instead of listing)
tin, low, it, on = [-1] * n, [0] * n, [0] * n, [False] * n
comp = [-1] * n
stack: list[int] = []
timer = ncomp = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer; timer += 1
stack.append(root); on[root] = True
call = [root]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if tin[v] == -1:
tin[v] = low[v] = timer; timer += 1
stack.append(v); on[v] = True
call.append(v)
elif on[v]:
low[u] = min(low[u], tin[v])
else:
call.pop()
if call:
low[call[-1]] = min(low[call[-1]], low[u])
if low[u] == tin[u]:
while True:
w = stack.pop(); on[w] = False; comp[w] = ncomp
if w == u:
break
ncomp += 1
# Tarjan numbers components in reverse topological order: every edge goes from a
# higher id to a lower or equal id, so increasing id = successors first.
total = [0] * ncomp
for v in range(n):
total[comp[v]] += coins[v]
succ: list[list[int]] = [[] for _ in range(ncomp)]
for u in range(n):
for v in adj[u]:
if comp[u] != comp[v]:
succ[comp[u]].append(comp[v])
best = [0] * ncomp
for c in range(ncomp):
best[c] = total[c] + max((best[d] for d in succ[c]), default=0)
return max(best, default=0)
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (2, 6), (6, 5), (6, 7), (4, 7)]
adj = [[] for _ in range(8)]
for u, v in edges:
adj[u].append(v)
assert max_coins(8, adj, [1, 2, 3, 4, 5, 6, 7, 8]) == 36 # A -> C -> B -> D
assert max_coins(3, [[], [], []], [5, 9, 2]) == 9 # no edges: best single vertex
print("condensation dp: ok")
Variant: minimum edges to make a digraph strongly connected
def min_edges_to_strongly_connect(n: int, comp: list[int], ncomp: int, adj: list[list[int]]) -> int:
if ncomp <= 1:
return 0
has_in = [False] * ncomp
has_out = [False] * ncomp
for u in range(n):
for v in adj[u]:
if comp[u] != comp[v]:
has_out[comp[u]] = True
has_in[comp[v]] = True
sources = sum(1 for c in range(ncomp) if not has_in[c])
sinks = sum(1 for c in range(ncomp) if not has_out[c])
return max(sources, sinks)
# 8-vertex example: SCC labels in Tarjan order {7}=0, {3,4,5}=1, {6}=2, {0,1,2}=3
comp = [3, 3, 3, 1, 1, 1, 2, 0]
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (2, 6), (6, 5), (6, 7), (4, 7)]
adj = [[] for _ in range(8)]
for u, v in edges:
adj[u].append(v)
assert min_edges_to_strongly_connect(8, comp, 4, adj) == 1 # add 7 -> 0
assert min_edges_to_strongly_connect(3, [0, 1, 2], 3, [[], [], []]) == 3 # three isolated vertices
assert min_edges_to_strongly_connect(3, [2, 1, 0], 3, [[1], [2], []]) == 1 # a chain: close it
print("min edges: ok")
Variant: recursion, if you must
In Python a recursive DFS needs a raised limit and a thread with a bigger stack; raising the limit alone turns a RecursionError into a crash when the C stack runs out.
# fragment — the recursion setup, not a full program
import sys, threading
sys.setrecursionlimit(1 << 20)
threading.stack_size(512 * 1024 * 1024) # 512 MB; the C stack is what actually overflows
threading.Thread(target=main).start()
In Java the equivalent is new Thread(null, runnable, "main", 1 << 28).start(). The iterative versions avoid the question entirely.
Real-world uses
- Network reliability. Bridges and articulation points are, literally, single points of failure in a topology: the one fibre link or the one router whose loss partitions the network. Operators of backbone and data-centre networks run this analysis on their topology graphs when planning redundancy, and "two edge-disjoint paths between every pair" is precisely 2-edge-connectivity. The routing side of the same networks is covered in BGP and the network layer; the graph algorithm tells you which links BGP has no alternative to.
- Compilers and call graphs. Mutually recursive functions form an SCC of the call graph. LLVM's
scc_iterator(inllvm/ADT/SCCIterator.h) is an implementation of Tarjan's algorithm and drives the call-graph SCC pass manager, which visits SCCs bottom-up so callees are optimised (and inlined) before callers — exactly the reverse topological order Tarjan produces for free. GHC similarly runs SCC analysis (itsDigraphmodule) over top-level bindings to group mutually recursive definitions before type inference. - Dependency resolution and build systems. A dependency cycle among packages or modules is an SCC of size greater than one; condensing it gives a DAG that can be topologically sorted into a build order, with each SCC built or loaded as a unit.
- Deadlock detection. A database's or OS's waits-for graph has a deadlock exactly when it has a cycle, i.e. a non-trivial SCC. The whole SCC names every transaction involved. See how databases work and concurrency patterns.
- The structure of the web. Broder et al., "Graph structure in the Web" (WWW 2000), ran SCC analysis on a crawl of about 200 million pages and found the "bow-tie": a giant SCC of about 56 million pages, with comparable "IN" and "OUT" sets that can only reach, or only be reached from, it. Link-analysis algorithms like PageRank behave differently on each part; graphs in the real world picks this up.
- 2-SAT. Satisfiability of a conjunction of two-literal clauses is decided by the SCCs of the implication graph in linear time: unsatisfiable iff some and share an SCC; see 2-SAT & colouring.
- Graph databases. Graph analytics libraries (Neo4j's Graph Data Science, for example) ship SCC and weakly-connected-component procedures; see graph databases.
Pitfalls & edge cases
- Skipping the parent vertex instead of the parent edge. False bridges on multigraphs. Use edge ids. (Articulation points survive either way, but use ids anyway so one routine does both.)
- Applying the non-root articulation rule to the root. A DFS root with one child is reported as a cut vertex. Count root children separately.
- Reporting a cut vertex once per child. A vertex can satisfy for several children; store a boolean, not a list append, or you get duplicates.
>versus>=. Bridges use strict against ; articulation points use . Swapping them is the most common bug, and the step-13 row of the trace is the counterexample to keep in mind.- Disconnected graphs. Loop over all vertices as potential roots. Each root gets its own root-children count.
- Self-loops. Harmless in the bridge code (seen as a back edge to itself, changes nothing); exclude them from block edge lists. A single vertex is its own SCC with or without one.
- Using
low[v]from a finished SCC in Tarjan. Forgetting theon_stackcheck lets cross edges into completed components lower low-links and merges distinct SCCs. The fix is the flag, not a different formula. - Recursion depth. A path graph with vertices crashes recursive DFS in Python and Java. Go iterative, or set up a big-stack thread properly.
- Iterative DFS that is not really DFS. "Push all neighbours, pop one" (the BFS-shaped stack loop) visits vertices in a DFS-like order but does not give correct discovery/finish times or tree edges, so low-links come out wrong. Keep a per-vertex neighbour index, as the code above does.
- Condensation edges duplicated. Harmless for max/min DP and reachability; deduplicate (or not) deliberately when counting paths.
- The min-edges formula on one SCC. If the whole graph is already one SCC the answer is 0, not . Special-case it.
- Overflow. Coin sums and DP values exceed 32 bits quickly ( rooms with coins each). Use 64-bit integers.
Variations
- Online bridges (incremental). Maintaining the number of bridges as edges are added one by one can be done in total with DSU over 2-edge-connected components plus a forest of bridge-tree parents; cp-algorithms has a full write-up, Finding bridges online.
- Strong orientation (Robbins' theorem, 1939). A connected undirected graph can have its edges oriented to make it strongly connected iff it has no bridge. Orient tree edges downward and back edges upward in a DFS. Codeforces "Bertown roads" is exactly this.
- Dominator trees. In a flow graph with a start vertex, dominates if every path from the start to passes through — the directed, single-source analogue of articulation points. Lengauer–Tarjan computes all dominators in near-linear time; compilers use them to build SSA form.
- Vertex and edge connectivity . "How many vertices must be removed to disconnect from ?" is a max-flow question by Menger's theorem; see network flow. Low-link handles only (cut vertices, bridges) and gives 2-connectivity as a by-product.
- Path-based SCC algorithms. Gabow's algorithm (2000) replaces low-link numbers with a second stack of path boundaries; same .
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Critical Connections in a Network (LeetCode 1192) — List every edge whose removal disconnects a connected network of servers. Teaches the bridge test with nothing else in the way.
Hint
Run the canonical routine and map bridge indices back to pairs. With up to , Python needs the iterative version.
2. Necessary Roads (CSES 2076) — Same as the previous problem on a road network, at contest scale. Teaches 1-based input and the parallel-edge trap if your code skips by vertex.
Hint
Bridges, printed as pairs. Use edge ids for the parent skip.
Solution
def necessary_roads(n: int, roads: list[tuple[int, int]]) -> list[tuple[int, int]]:
"""roads are 1-based; returns the bridges as 1-based pairs, in input order."""
adj = [[] for _ in range(n + 1)]
for i, (a, b) in enumerate(roads):
adj[a].append((b, i))
adj[b].append((a, i))
tin, low, pe, it = [-1] * (n + 1), [0] * (n + 1), [-1] * (n + 1), [0] * (n + 1)
bridge = [False] * len(roads)
timer = 0
for root in range(1, n + 1):
if tin[root] != -1:
continue
tin[root] = low[root] = timer; timer += 1
stack = [root]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v, e = adj[u][it[u]]; it[u] += 1
if e == pe[u]:
continue
if tin[v] == -1:
tin[v] = low[v] = timer; timer += 1
pe[v] = e
stack.append(v)
else:
low[u] = min(low[u], tin[v])
else:
stack.pop()
if stack:
p = stack[-1]
low[p] = min(low[p], low[u])
if low[u] > tin[p]:
bridge[pe[u]] = True
return [roads[i] for i in range(len(roads)) if bridge[i]]
assert necessary_roads(5, [(1, 2), (1, 3), (3, 4), (1, 4), (4, 5)]) == [(1, 2), (4, 5)]
assert necessary_roads(2, [(1, 2), (1, 2)]) == []
print("necessary roads ok")
time and memory.
3. Necessary Cities (CSES 2077) — List every city whose removal disconnects the network. Teaches the articulation test and the root rule.
Hint
Same DFS; a non-root is critical if some child has ; the root only if it has at least two tree children. Deduplicate.
4. Flight Routes Check (CSES 1682) — Decide whether every city can fly to every other; if not, print a pair that fails. Teaches that "one SCC?" needs only two BFS runs.
Hint
BFS from city 1 in the graph and in the reversed graph. A city missed in the first gives the pair (1, city); missed in the second gives (city, 1).
5. Planets and Kingdoms (CSES 1683) — Label each planet with its kingdom, where a kingdom is a set of planets that can all reach each other. Teaches plain SCC labelling.
Hint
Tarjan or Kosaraju; output component ids in any consistent numbering.
Solution
def kingdoms(n: int, routes: list[tuple[int, int]]) -> tuple[int, list[int]]:
adj = [[] for _ in range(n)]
for a, b in routes:
adj[a - 1].append(b - 1)
tin, low, it, on = [-1] * n, [0] * n, [0] * n, [False] * n
comp = [0] * n
stack, timer, k = [], 0, 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer; timer += 1
stack.append(root); on[root] = True
call = [root]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if tin[v] == -1:
tin[v] = low[v] = timer; timer += 1
stack.append(v); on[v] = True; call.append(v)
elif on[v]:
low[u] = min(low[u], tin[v])
else:
call.pop()
if call:
low[call[-1]] = min(low[call[-1]], low[u])
if low[u] == tin[u]:
k += 1
while True:
w = stack.pop(); on[w] = False; comp[w] = k
if w == u:
break
return k, comp
k, comp = kingdoms(5, [(1, 2), (2, 3), (3, 1), (3, 4), (4, 5), (5, 4)])
assert k == 2 and comp[0] == comp[1] == comp[2] and comp[3] == comp[4] and comp[0] != comp[3]
print("planets and kingdoms ok")
.
6. Checkposts (Codeforces 427C) — Place police checkposts so that every junction is protected, at minimum total cost, and count the optimal placements. Teaches per-SCC aggregation: one checkpost per SCC suffices and is necessary.
Hint
For each SCC take its minimum cost and the number of junctions achieving it. Sum the minima; multiply the counts modulo .
Solution
def checkposts(n: int, cost: list[int], roads: list[tuple[int, int]]) -> tuple[int, int]:
MOD = 10**9 + 7
adj = [[] for _ in range(n)]
for a, b in roads:
adj[a - 1].append(b - 1)
tin, low, it, on = [-1] * n, [0] * n, [0] * n, [False] * n
stack, timer = [], 0
total, ways = 0, 1
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer; timer += 1
stack.append(root); on[root] = True
call = [root]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if tin[v] == -1:
tin[v] = low[v] = timer; timer += 1
stack.append(v); on[v] = True; call.append(v)
elif on[v]:
low[u] = min(low[u], tin[v])
else:
call.pop()
if call:
low[call[-1]] = min(low[call[-1]], low[u])
if low[u] == tin[u]:
best, cnt = None, 0
while True:
w = stack.pop(); on[w] = False
if best is None or cost[w] < best:
best, cnt = cost[w], 1
elif cost[w] == best:
cnt += 1
if w == u:
break
total += best
ways = ways * cnt % MOD
return total, ways
assert checkposts(3, [1, 2, 3], [(1, 2), (2, 3), (3, 2)]) == (3, 1)
assert checkposts(2, [7, 91], [(1, 2), (2, 1)]) == (7, 1)
assert checkposts(3, [2, 2, 5], [(1, 2), (2, 1), (2, 3)]) == (7, 2)
print("checkposts ok")
.
7. Reachability from the Capital (Codeforces 999E) — Add the fewest one-way roads so every city is reachable from the capital. Teaches counting condensation sources.
Hint
Condense. Every source SCC other than the capital's needs one new incoming road (from the capital), and that is enough: the answer is the number of in-degree-0 components excluding the capital's.
8. Coin Collector (CSES 1686) — Walk through rooms along one-way tunnels, collecting coins, revisiting allowed; maximise the total. Teaches condensation plus longest-path DP.
Hint
Collect a whole SCC at once. DP over components in Tarjan's emission order (successors first). 64-bit sums.
Solution
The max_coins variant above is the full solution (convert input to 0-based). Here is a Kosaraju-based version checked against a brute force over tiny graphs:
import random
from itertools import permutations
def coin_collector(n: int, coins: list[int], tunnels: list[tuple[int, int]]) -> int:
adj = [[] for _ in range(n)]
for a, b in tunnels:
adj[a - 1].append(b - 1)
# Kosaraju with labels in topological order, then DP in reverse topological order
seen, order = [False] * n, []
for s in range(n):
if seen[s]:
continue
seen[s] = True
st = [(s, 0)]
while st:
u, i = st[-1]
if i < len(adj[u]):
st[-1] = (u, i + 1)
v = adj[u][i]
if not seen[v]:
seen[v] = True
st.append((v, 0))
else:
st.pop()
order.append(u)
radj = [[] for _ in range(n)]
for u in range(n):
for v in adj[u]:
radj[v].append(u)
comp, k = [-1] * n, 0
for s in reversed(order):
if comp[s] != -1:
continue
comp[s] = k
st = [s]
while st:
u = st.pop()
for v in radj[u]:
if comp[v] == -1:
comp[v] = k
st.append(v)
k += 1
total = [0] * k
for v in range(n):
total[comp[v]] += coins[v]
best = total[:]
succ = [set() for _ in range(k)]
for u in range(n):
for v in adj[u]:
if comp[u] != comp[v]:
succ[comp[u]].add(comp[v])
for c in range(k - 1, -1, -1): # Kosaraju ids are topological: successors have larger ids
best[c] = total[c] + max((best[d] for d in succ[c]), default=0)
return max(best)
def brute(n, coins, tunnels):
adj = [[] for _ in range(n)]
for a, b in tunnels:
adj[a - 1].append(b - 1)
reach = [[False] * n for _ in range(n)]
for s in range(n):
reach[s][s] = True
st = [s]
while st:
u = st.pop()
for v in adj[u]:
if not reach[s][v]:
reach[s][v] = True
st.append(v)
# a set of rooms is collectable iff some ordering visits them along reachability
best = 0
for mask in range(1, 1 << n):
rooms = [v for v in range(n) if mask >> v & 1]
for perm in permutations(rooms):
if all(reach[perm[i]][perm[i + 1]] for i in range(len(perm) - 1)):
best = max(best, sum(coins[v] for v in rooms))
break
return best
assert coin_collector(4, [4, 5, 2, 7], [(1, 2), (2, 1), (1, 3), (2, 4)]) == 16
random.seed(7)
for _ in range(200):
n = random.randint(1, 6)
tunnels = [(random.randint(1, n), random.randint(1, n)) for _ in range(random.randint(0, 8))]
coins = [random.randint(1, 9) for _ in range(n)]
assert coin_collector(n, coins, tunnels) == brute(n, coins, tunnels)
print("coin collector ok")
for the real solution; the brute force is only for checking.
9. Proving Equivalences (Kattis) — Some implications between statements are already proved; find the fewest extra implications that make all statements equivalent. Teaches the formula and its one-SCC special case.
Hint
Condense, count in-degree-0 and out-degree-0 components, answer of the two, or 0 if there is a single component.
Solution
def proving_equivalences(n: int, implications: list[tuple[int, int]]) -> int:
adj = [[] for _ in range(n)]
for a, b in implications:
adj[a - 1].append(b - 1)
tin, low, it, on = [-1] * n, [0] * n, [0] * n, [False] * n
comp = [-1] * n
stack, timer, k = [], 0, 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer; timer += 1
stack.append(root); on[root] = True
call = [root]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if tin[v] == -1:
tin[v] = low[v] = timer; timer += 1
stack.append(v); on[v] = True; call.append(v)
elif on[v]:
low[u] = min(low[u], tin[v])
else:
call.pop()
if call:
low[call[-1]] = min(low[call[-1]], low[u])
if low[u] == tin[u]:
while True:
w = stack.pop(); on[w] = False; comp[w] = k
if w == u:
break
k += 1
if k == 1:
return 0
has_in, has_out = [False] * k, [False] * k
for u in range(n):
for v in adj[u]:
if comp[u] != comp[v]:
has_out[comp[u]] = has_in[comp[v]] = True
return max(has_in.count(False), has_out.count(False))
assert proving_equivalences(4, []) == 4
assert proving_equivalences(3, [(1, 2), (1, 3)]) == 2
assert proving_equivalences(3, [(1, 2), (2, 3), (3, 1)]) == 0
print("proving equivalences ok")
.
10. New Flight Routes (CSES 1685) — Same count as the previous problem, but you must also print the new routes. Teaches that the formula is easy and the construction is not.
Hint
Follow the Eswaran–Tarjan construction: match each source to a sink it reaches (DFS from unmatched sources), chain the matched pairs into a cycle, then attach the leftover sources and sinks. Test with isolated vertices.
11. Bertown Roads (Codeforces 118E) — Orient every two-way road so the city stays strongly connected, or report that it is impossible. Teaches Robbins' theorem.
Hint
Impossible iff there is a bridge. Otherwise orient tree edges parent-to-child and back edges descendant-to-ancestor, in the order the DFS first traverses them.
12. We Need More Bosses (Codeforces 1000E) — Choose two locations to maximise the number of passages that every route between them must use. Teaches the bridge tree.
Hint
Contract 2-edge-connected components; the bridge tree's diameter (two BFS runs) is the answer.
13. Tourist Reform (Codeforces 732F) — Orient all roads to maximise the minimum, over cities, of the number of cities reachable. Teaches combining 2-edge-connected components with a rooted bridge tree.
Hint
The largest 2-edge-connected component can be made strongly connected internally; orient every bridge toward it, so every city reaches it. The answer is its size.
14. Minimum Number of Days to Disconnect Island (LeetCode 1568) — Turn land cells to water to split a grid island; find the minimum number of days. Teaches that the answer is always 0, 1 or 2, with 1 iff the island has an articulation cell (or is a single cell).
Hint
0 if already not exactly one island. Otherwise build the grid graph on land cells and check for an articulation point (or a one-cell island): answer 1. Else 2 — any corner cell of the island can be cut off by removing its at most two land neighbours.
Common mistakes & interview follow-ups
"Why is skipping the parent vertex wrong?" With two parallel edges between and , the second is a back edge that makes the pair a 2-cycle; skipping by vertex ignores it and reports a false bridge. Skip the entering edge's id.
"Why does the root need a special case?" is the minimum, so always holds. The root separates the graph exactly when it has two or more DFS children, because undirected DFS has no cross edges between child subtrees.
"Tarjan or Kosaraju?" Tarjan: one pass, no reverse graph, gives reverse topological order — usually faster and what you want for condensation DP. Kosaraju: easier to remember and to prove, gives topological order, needs . Both .
"What if the graph does not fit in memory?" Low-link DFS needs random access. Parallel and distributed systems use forward-backward (FW-BW) decomposition instead: pick a pivot, intersect its forward and backward reachable sets (one SCC), recurse on the rest. More total work in the worst case, but it parallelises.
"What if edges arrive over time?" Incremental bridges: DSU on 2-edge-connected components (cp-algorithms). Fully dynamic SCCs are a research topic; "recompute in per batch" is the honest interview answer.
"Can you make the graph 2-edge-connected by adding edges?" With leaves in the bridge tree, edges (pair the leaves up in DFS order).
Common mistakes interviewers watch for: pseudo-DFS with a stack that pushes all neighbours at once; forgetting the on_stack check; > vs >=; not looping over all roots; recursive Python on a path.
Quick quiz
1. In the 7-vertex example, add the edge . Which edges are bridges now and which vertices are cut vertices?
Answer
Only remains a bridge. The new edge puts on the cycle , so the subtree of 6 now climbs to . Cut vertices: 1 and 3. Vertex 5 is no longer one, because 6 can reach 4 without passing through 5.
2. A DFS root has exactly one child , and . Is the root a cut vertex?
Answer
No. The root rule counts children, not low-links: with one child, removing the root leaves that child's subtree, which is connected.
3. Tarjan's algorithm emits SCCs in the order . In which order should you process them to compute "longest path starting in each component"?
Answer
In emission order first. Tarjan emits a component only after every component reachable from it has been emitted, so is a reverse topological order and successors are always ready.
4. A condensation has 3 sources, 5 sinks and 7 components. How many edges must be added to make the graph strongly connected?
Answer
. (If it had 1 component the answer would be 0.)
5. Why can't you replace tin[v] with low[v] for back edges in the articulation-point algorithm, even though it is harmless in Tarjan's SCC algorithm?
Answer
Suppose the only back edge out of child 's subtree goes to itself. With tin[p] it gives , and correctly flags . With low[p], which may already be smaller because of a back edge from 's other branch, 's subtree "borrows" an escape route that starts at — useless once is deleted — so is wrongly cleared. The proofs rely on the definition: at most one back edge, starting inside the subtree.
Further reading / sources
- Robert E. Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1(2):146–160, 1972 — low-link, SCCs, biconnected components.
- John Hopcroft and Robert Tarjan, "Algorithm 447: Efficient algorithms for graph manipulation", Communications of the ACM 16(6):372–378, 1973.
- M. Sharir, "A strong-connectivity algorithm and its applications in data flow analysis", Computers & Mathematics with Applications 7(1):67–72, 1981 (the two-pass algorithm usually credited to Kosaraju).
- K. P. Eswaran and R. E. Tarjan, "Augmentation problems", SIAM Journal on Computing 5(4):653–665, 1976 — minimum edges for strong connectivity and 2-connectivity.
- H. E. Robbins, "A theorem on graphs, with an application to a problem of traffic control", American Mathematical Monthly 46(5):281–283, 1939.
- CLRS, Introduction to Algorithms, 4th ed., chapter 20 "Elementary Graph Algorithms" (DFS, edge classification, white-path theorem, SCCs via the two-pass algorithm) and problem 20-2 "Articulation points, bridges, and biconnected components".
- cp-algorithms: Finding bridges, Finding articulation points, Strongly connected components and condensation graph, Finding bridges online.
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 17 "Strong connectivity".
- Andrei Broder et al., "Graph structure in the Web", Computer Networks 33(1–6), 2000 (WWW9).
Previous lesson: Minimum Spanning Trees: Kruskal, Prim & Boruvka · Next lesson: Euler & Hamiltonian Paths
Related: Graphs overview · DFS in Depth · Topological Sort & DAG DP · Union-Find in Depth · 2-SAT & colouring · Network Flow · LCA & Binary Lifting · Graph databases · Course home