Bridges and articulation points

Why this matters when you build with AI

Ask an AI tool for "the critical edges of a network" and you often get a recursive depth-first search (DFS) that checks low[to] > tin[v] and skips the parent by vertex. Both pieces can be wrong in a way that passes a small test. The parent skip breaks on parallel edges, which are two edges between the same pair of vertices. The root rule is missing, so a single edge gets reported as a cut vertex. The recursion can overflow on a long path, and the program then crashes with no useful message.

You catch these in a few minutes. Test two vertices joined by two parallel edges, a single edge, a triangle, and a long path. A correct answer for the first is "no bridges". For the second, "no cut vertices". For the triangle, "no bridges". For the long path, the program must finish without a crash. The lesson shows how to write the search so these cases pass, and how to check it against a slow method that you can trust.

A prompt that states the requirements:

Write a C++17 function that takes an undirected multigraph with n vertices and m edges
(parallel edges allowed, no self-loops). Return, for each edge, whether it is a bridge,
and for each vertex, whether it is an articulation point. Use an iterative DFS so that a
path of 300000 vertices does not overflow the stack. Skip the parent edge by edge id, not
by vertex. Explain the root rule for articulation points in one sentence.

A good answer uses edge ids for the parent skip, has a stack of frames instead of recursion, and treats the DFS root with its own rule. Check each of these in the code, then run the comparison in "Check them against each other".

Terms used

An undirected graph is a set of vertices joined by edges with no direction. An edge u v can be walked both ways.
A multigraph allows two or more edges between the same pair of vertices. These are called parallel edges.
A connected component is a group of vertices where every vertex can reach every other one.
A bridge is an edge whose removal increases the number of connected components. In a power grid, it is a cable whose cut leaves some substation with no power.
An articulation point (also called a cut vertex) is a vertex whose removal, along with its edges, increases the number of components among the other vertices.
A DFS tree is the set of edges the search used to first reach each vertex. The other edges of the graph are called back edges, because they go from a vertex to one of its ancestors in the tree.
tin[v] is the step number at which the DFS first enters v. Steps count from 0.
low[v] is the smallest tin value that v can reach by going down its subtree and then using at most one back edge. It is the lowest entry time v can see.
A 2-edge-connected component is a group of vertices with no bridge between them. Removing any single edge keeps them connected.
The bridge tree is a tree with one node per 2-edge-connected component and one edge per bridge.

The idea: low-link values

Take a small example first. Vertices 0, 1 and 2 form a triangle. Vertex 2 has another neighbour, 3, and 3 is the start of a path. Here the search starts at 0.

0 -> 1,  1 -> 2,  2 -> 0,  2 -> 3

The DFS enters 0 at step 0, then goes to 1 (step 1), then to 2 (step 2). From 2 it sees the edge back to 0. Vertex 0 was entered at step 0, so low[2] becomes 0. The edge 2 to 3 leads to a new vertex, so the search enters 3 at step 3. Vertex 3 has no way back above itself, so low[3] stays 3.

Now the rule. For a tree edge from parent p to child v (the edge the search used to enter v):

The edge is a bridge if low[v] > tin[p]. This means v's subtree cannot reach p or anything above p, except through this edge. Remove it and the subtree is cut off.
For the triangle edges, low[2] is 0, which is less than tin[1] = 1, so the edge 1 to 2 is not a bridge. Good.
For the edge 2 to 3, low[3] is 3, which is greater than tin[2] = 2, so 2 to 3 is a bridge. Good.

For articulation points, the rule is about children. For a vertex p that is not the DFS root, p is an articulation point if some child v has low[v] >= tin[p]. The child's subtree cannot get above p without going through p. Note the >=. If low[v] equals tin[p], the subtree reaches p but nothing above p, so removing p cuts the subtree off from the rest of the graph.

The DFS root is different. Every child of the root has low[child] >= tin[root], because the root has the smallest entry time. So the condition is always true for the root, and it would mark every root as a cut vertex. The correct rule for the root: it is an articulation point if and only if it has two or more DFS children. A single child gives a subtree that can only reach the root, so the root is a leaf in the sense that matters here.

A trace on the worked example

The header below prints tin and low for the example graph in the next section (vertices 0 to 6, edges 0-1, 1-2, 2-0, 1-2, 2-3, 3-4, 4-5, 5-3, 5-6). This is real output from the program:

v=0 tin=0 low=0
v=1 tin=1 low=0
v=2 tin=2 low=0
v=3 tin=3 low=3
v=4 tin=4 low=3
v=5 tin=5 low=3
v=6 tin=6 low=6

Read it with the rules. Edge 2 to 3 is a bridge, because low[3] = 3 is greater than tin[2] = 2. Edge 5 to 6 is a bridge, because low[6] = 6 is greater than tin[5] = 5. Vertex 2 is an articulation point, because its child 3 has low[3] = 3 >= tin[2] = 2. The root 0 has one DFS child (vertex 1), so it is not an articulation point.

The numbers depend on the order in which the edges are stored. A different edge order gives different tin values. The bridges and cut vertices do not change, because they are properties of the graph.

Why parallel edges need edge ids

Suppose the graph has two edges between vertices 0 and 1. The search goes from 0 to 1 along edge A and then looks at the edges of 1. It finds edge B, which also leads to 0. If the search skips the parent by vertex (any edge to the parent is ignored), it skips edge B too. Then low[1] stays at 1, and the tree edge A is reported as a bridge. That is wrong: removing A alone leaves 0 and 1 joined by B.

The fix is to skip only the one edge we came in by, identified by its id. Edge B has a different id, so it is treated as a back edge and lowers low[1] to 0. Then A is not a bridge.

This detail is the one most often wrong in code written by AI tools.

Iterative DFS

A recursive DFS calls itself once per vertex on the current path. Each call uses some stack memory. A path of 300000 vertices needs 300000 nested calls. The stack limit depends on the judge and the operating system, so the recursive version can work on one machine and crash on another with a segmentation fault and no message about the reason.

The iterative version keeps the same state in a vector. Each frame holds the vertex, the edge id it came in by, and the index of the next neighbour to try. The loop looks at the top frame. If it has a neighbour left, it either pushes a new frame (for an unvisited neighbour) or updates low (for a visited one). If it has no neighbours left, it pops the frame and updates the parent's low with the child's. This is the same algorithm as the recursive one, with the call stack written out by hand.

One detail matters. When the code pushes a new frame, the vector may move in memory. So the code must not keep a reference to the top frame across a push. The header copies the values it needs before pushing.

The C++17 code

The header is bridges.hpp. It holds the graph type, the search that finds bridges and cut vertices, and the bridge tree. The search takes O(n + m) time.

// bridges.hpp: bridges, articulation points and the bridge tree of an undirected multigraph.
// Iterative DFS, so a long path does not overflow the call stack. Self-loops are not supported.
#pragma once
#include <algorithm>
#include <utility>
#include <vector>
 
struct UGraph {
    int n = 0;
    std::vector<std::pair<int, int>> edges;            // edge id -> (u, v)
    std::vector<std::vector<std::pair<int, int>>> adj;  // v -> (neighbour, edge id)
 
    explicit UGraph(int n_) : n(n_), adj(n_) {}
    int add_edge(int u, int v) {
        int id = (int)edges.size();
        edges.push_back({u, v});
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
        return id;
    }
};
 
struct BridgeInfo {
    std::vector<int> is_bridge;   // per edge id: 1 if removing it disconnects its component
    std::vector<int> is_art;      // per vertex: 1 if removing it disconnects its component
    std::vector<int> tin, low;    // DFS entry time and low-link value
};
 
BridgeInfo find_bridges(const UGraph& g) {
    int n = g.n, m = (int)g.edges.size();
    BridgeInfo r;
    r.is_bridge.assign(m, 0);
    r.is_art.assign(n, 0);
    r.tin.assign(n, -1);
    r.low.assign(n, -1);
 
    struct Frame {
        int v;      // vertex
        int pe;     // id of the edge we came in by, -1 for a DFS root
        int it;     // next index in adj[v] to look at
    };
    std::vector<Frame> st;
    int timer = 0;
 
    for (int s = 0; s < n; s++) {
        if (r.tin[s] != -1) continue;
        int root_children = 0;
        r.tin[s] = r.low[s] = timer++;
        st.push_back({s, -1, 0});
        while (!st.empty()) {
            int v = st.back().v;
            int pe = st.back().pe;
            if (st.back().it < (int)g.adj[v].size()) {
                auto [to, id] = g.adj[v][st.back().it++];
                if (id == pe) continue;  // skip only the edge we came by, so parallel edges still count
                if (r.tin[to] == -1) {
                    r.tin[to] = r.low[to] = timer++;
                    st.push_back({to, id, 0});  // no reference to st.back() is used after this push
                } else {
                    r.low[v] = std::min(r.low[v], r.tin[to]);  // back edge to an ancestor
                }
            } else {
                st.pop_back();
                if (st.empty()) break;
                int p = st.back().v;
                r.low[p] = std::min(r.low[p], r.low[v]);
                if (r.low[v] > r.tin[p]) r.is_bridge[pe] = 1;
                if (st.back().pe == -1) {
                    root_children++;  // p is the DFS root
                } else if (r.low[v] >= r.tin[p]) {
                    r.is_art[p] = 1;
                }
            }
        }
        if (root_children >= 2) r.is_art[s] = 1;
    }
    return r;
}
 
struct BridgeTree {
    int count = 0;                      // number of 2-edge-connected components
    std::vector<int> comp;              // vertex -> component id
    std::vector<std::pair<int, int>> tree_edges;  // one per bridge, as (component, component)
};
 
// Two vertices are in the same 2-edge-connected component if no bridge separates them.
// Components are found by a search that does not cross bridges. The bridges form a forest.
BridgeTree build_bridge_tree(const UGraph& g, const BridgeInfo& info) {
    BridgeTree t;
    t.comp.assign(g.n, -1);
    std::vector<int> stack;
    for (int s = 0; s < g.n; s++) {
        if (t.comp[s] != -1) continue;
        int c = t.count++;
        t.comp[s] = c;
        stack.push_back(s);
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            for (auto [to, id] : g.adj[v]) {
                if (info.is_bridge[id] || t.comp[to] != -1) continue;
                t.comp[to] = c;
                stack.push_back(to);
            }
        }
    }
    for (int id = 0; id < (int)g.edges.size(); id++) {
        if (!info.is_bridge[id]) continue;
        auto [u, v] = g.edges[id];
        t.tree_edges.push_back({t.comp[u], t.comp[v]});
    }
    return t;
}

The demo program reads a graph and prints what the header finds. It is demo.cpp:

// demo.cpp: reads "n m" then m lines "u v", prints bridges, articulation points and the bridge tree.
#include <cstdio>
#include "bridges.hpp"
 
int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    UGraph g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        if (scanf("%d %d", &u, &v) != 2) return 1;
        g.add_edge(u, v);
    }
    BridgeInfo info = find_bridges(g);
    printf("bridges:");
    for (int id = 0; id < m; id++)
        if (info.is_bridge[id]) printf(" %d(%d-%d)", id, g.edges[id].first, g.edges[id].second);
    printf("\n");
    printf("articulation points:");
    for (int v = 0; v < n; v++)
        if (info.is_art[v]) printf(" %d", v);
    printf("\n");
    BridgeTree t = build_bridge_tree(g, info);
    printf("2-edge-connected components: %d\n", t.count);
    for (int v = 0; v < n; v++) printf("vertex %d -> component %d\n", v, t.comp[v]);
    printf("bridge tree edges:");
    for (auto [a, b] : t.tree_edges) printf(" (%d,%d)", a, b);
    printf("\n");
    return 0;
}

Compile and run it with:

g++ -O2 -std=c++17 -Wall -Wextra -o demo demo.cpp && ./demo < example.txt

Worked example: a power grid

A small town has seven substations, numbered 0 to 6. Two cables join substations 1 and 2, so the cables are parallel. The input file example.txt is:

The task: which cables, if cut, leave some substation without power? Which substations, if they fail, split the grid? And what does the grid look like when every 2-edge-connected block is shrunk to one node?

Work it by hand first. Substations 0, 1 and 2 are tied together by the triangle and the parallel cable, so no one cable among them is critical. Substations 3, 4 and 5 form a triangle too. The cable 2 to 3 joins the two blocks, so cutting it splits the grid. The cable 5 to 6 is the only way to reach substation 6, so cutting it isolates 6. Substation 2 is the only link between and the rest, so it is a cut point. Substation 3 is the only link between and . Substation 5 is the only link to 6.

Real output of the program:

bridges: 4(2-3) 8(5-6)
articulation points: 2 3 5
2-edge-connected components: 3
vertex 0 -> component 0
vertex 1 -> component 0
vertex 2 -> component 0
vertex 3 -> component 1
vertex 4 -> component 1
vertex 5 -> component 1
vertex 6 -> component 2
bridge tree edges: (0,1) (1,2)

The output matches the hand work. Edge ids are the input order, starting at 0, so id 4 is the cable 2 to 3, and id 8 is the cable 5 to 6. The parallel cables (ids 1 and 3) are not bridges.

Bridge tree

Remove every bridge from the graph. The pieces left are the 2-edge-connected components. Draw one node per piece and one edge per bridge. The result is always a forest (a set of trees). For this grid it is a single tree with three nodes: {0, 1, 2}, {3, 4, 5} and {6}, joined in a chain.

The bridge tree is useful because it turns a question about the whole graph into a question about a tree. For example, to make the grid survive any single cable cut, you can add cables. In this grid, the two leaves of the bridge tree are {0, 1, 2} and {6} (a leaf is a node with one bridge). Adding the cable 0 to 6 removes both bridges. Running the program on the example with that cable added prints bridges: and articulation points: with nothing after them. This lesson does not prove that a single cable is enough for a tree with more leaves, so check that on your own input.

Check them against each other

The header is checked against brute force. Brute force means a slow method that is easy to trust. For bridges, remove one edge and count the components with a disjoint set union. An edge is a bridge if the count goes up. For articulation points, remove one vertex and its edges, and check whether the count of the other vertices' components goes up compared with the original graph. The vertex is an articulation point if the count rises above the original number of components.

The stress program stress.cpp makes random multigraphs with 1 to 8 vertices and up to 12 edges, and it allows parallel edges. It compares every edge and every vertex with the brute force, and it checks that every bridge tree has one edge per bridge. Real output:

ok seed=1 tests=5000 bridges_checked=4851 articulation_checked=3565 parallel_graphs=2784
ok seed=2024 tests=5000 bridges_checked=4367 articulation_checked=3304 parallel_graphs=2786
ok seed=77 tests=8000 bridges_checked=7576 articulation_checked=5598 parallel_graphs=4490

About half of the random graphs had parallel edges, so the parallel-edge case is covered.

A deep test checks the iterative version. The file deep.cpp builds a path of 300000 vertices and closes a cycle on the last three. Real output:

n=300000 bridges=299997 articulation=299997 components=299998

By hand: the path has 299999 edges, and three of them lie on the cycle, so 299999 minus 2 leaves 299997 bridges. Every vertex from 1 to 299997 is a cut vertex, which also gives 299997. Components equal bridges plus one, which is 299998. The recursive version of this program would need 300000 nested calls. Whether it crashes depends on your stack limit, so run it on your own machine before you rely on it.

To check that the stress test can catch a wrong program, four wrong variants were made by changing one line each, and each one ran through the stress test with seed 1:

Skipping the parent by vertex (to == parent) instead of by edge id. It failed at test 6: FAIL bridge test=6 edge=0 brute=0 fast=1.
Using >= instead of > for the bridge test. It failed at test 0: FAIL bridge test=0 edge=0 brute=0 fast=1.
Applying the child rule to the root too. It failed at test 0: FAIL articulation test=0 vertex=0 brute=0 fast=1.
Leaving out the update of the parent's low after a child finishes. The stress run was not repeated for this one; its wrong output on the example is shown in "Common mistakes".

Complexity

Time is O(n + m), because each vertex is entered once and each edge is looked at twice (once from each end). Memory is O(n + m). The time figure is a bound from the algorithm. I did not time the program on a large graph, so treat the speed as untested on your machine.

Common mistakes

Mistake 1: skipping the parent by vertex. On the input 2 2 / 0 1 / 0 1 the correct output is no bridges. The wrong version prints bridges: 0(0-1), because edge 0 and edge 1 both connect 0 and 1, and the skip removed the second one too. The symptom in a contest is a wrong answer on a test that has double roads. Fix: skip by edge id.

Mistake 2: no root rule. On the single edge 2 1 / 0 1 the correct output is articulation points: with nothing listed. The wrong version (the child rule applied to the root) prints articulation points: 0. The root has one child, and removing the root leaves a single subtree, so it is not a cut vertex. Fix: count root children and require at least two.

Mistake 3: >= in the bridge test. On the triangle 3 3 / 0 1 / 1 2 / 2 0 the correct output has no bridges. With >=, the wrong version reports the edge 0 to 1 as a bridge. The >= test is right for articulation points and wrong for bridges. The two tests use different comparisons.

Mistake 4: recursion on a long path. The symptom is a segmentation fault on a long path, while short inputs pass. I did not reproduce the crash in this lesson, because the depth that causes it depends on the stack limit (run ulimit -s to see yours). Fix: use the frame stack shown above.

Mistake 5: forgetting to update the parent after a child finishes. If the code does not do low[p] = min(low[p], low[v]) when v is popped, the parent's low value stays too high. Then a cable that lies on a cycle can look like a bridge. I checked this with a copy of the header with that one line removed. On the worked example it printed bridges: 0(0-1) 4(2-3) 5(3-4) 8(5-6). The correct answer has only 4 and 8. Cables 0 to 1 and 3 to 4 lie on cycles, so they are not bridges.

Mistake 6: self-loops. The header is not tested with edges from a vertex to itself. Such an edge does not change connectivity, so drop self-loops from the input before building the graph.

Checklist

Parent skip by edge id, never by vertex.
Bridge test: low[child] > tin[parent].
Articulation test for non-root vertices: low[child] >= tin[parent].
Root: articulation point only with two or more DFS children.
Update the parent's low when a child finishes.
Use an explicit stack for the DFS on any input that can be a long path.
Drop self-loops, or handle them before the search.
Test on two parallel edges, a single edge, a triangle and a path.
Compare with the brute force on at least a few thousand random small graphs.

What was checked

All C++ code compiled with g++ 15.2.0 (Ubuntu) using -O2 -std=c++17 -Wall -Wextra. The demo and stress programs compiled with no warnings after one fix, which replaced an unchecked scanf with a checked one.
stress passed on 5000 graphs with seed 1, 5000 with seed 2024, and 8000 with seed 77. Each graph has 1 to 8 vertices, up to 12 edges, and may have parallel edges. The brute force is described above.
Three wrong variants (skip by vertex, >= for bridges, root rule missing) were each run through the stress test with seed 1, and each one failed. The variant with the parent's low not updated was run only on the worked example. The outputs in "Common mistakes" come from running the variants on the inputs shown.
The deep test ran on a path of 300000 vertices with the iterative header. It passed on the machine used for this lesson. I did not test a recursive version to show where it crashes.
The worked example, the trace, and the practice answers come from program runs.
The bridge tree leaf count in the worked example is my own reading of the output. The claim that the leaf count gives a minimum number of new cables is not proved here, so the lesson says to check it.
The citation is R. E. Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing, volume 1, issue 2, pages 146 to 160, 1972. I confirmed the bibliographic record in search results. I did not read the full text, so the lesson uses the paper only for the low-link method in general terms.

Summary

A DFS gives each vertex an entry time and a low-link value. An edge to a child is a bridge when the child's low value is above the parent's entry time. A non-root vertex is a cut vertex when some child's low value is at or above its entry time, and the root needs two children. Parallel edges require skipping by edge id, and the search should use an explicit stack. The bridges split the graph into 2-edge-connected blocks, and those blocks form a tree.

Practice

Problem 1: which cable isolates a substation

Use the example grid in example.txt. Which single cable, if cut, leaves substation 6 with no connection to the rest of the grid? Give the edge id.

Show the answer

Hint: a substation with one cable is a leaf. Look at the bridge list.

Answer: edge id 8, the cable 5 to 6. The program printed bridges: 4(2-3) 8(5-6), and only 8 touches substation 6.

Problem 2: add one cable

Add a cable from substation 0 to substation 3 to the example. The new cable gets id 9. Which bridges and cut vertices remain? Check with the program, and then explain why 2 is no longer a cut vertex.

Show the answer

Hint: a new edge makes a new cycle. Which vertices lie on it?

Answer: the output is bridges: 8(5-6) and articulation points: 3 5. Cable 2 to 3 is no longer a bridge, because the cycle 0 to 2 to 3 to 0 now covers it. Vertex 2 is no longer a cut vertex for the same reason: substations 0 and 1 can now reach 3 without going through 2. Vertex 3 is still a cut point, because 4, 5 and 6 are reached from the rest only through 3. Vertex 5 is still a cut point, because 6 hangs off it.

Real output (file p2.txt):

bridges: 8(5-6)
articulation points: 3 5
2-edge-connected components: 2

Problem 3: the parallel trap

The input 3 3 / 0 1 / 0 1 / 1 2 has a double cable between 0 and 1 and a single cable from 1 to 2. Which edges are bridges, and which vertex is a cut vertex? Then say what the skip-by-vertex version would print for the bridges.

Show the answer

Hint: which of the two cables between 0 and 1 is needed to keep 0 connected?

Answer: edge id 2 (the cable 1 to 2) is the only bridge. Vertex 1 is the only cut vertex, because removing it separates 2 from 0. The two cables between 0 and 1 are not bridges. The skip-by-vertex version would print bridges: 0(0-1) 2(1-2), which is wrong for edge 0. Real output from the program (file p3.txt):

bridges: 2(1-2)
articulation points: 1

Problem 4: count the leaves of the bridge tree

In the example, the bridge tree has three nodes and two edges. How many of its nodes have exactly one edge? Explain why this count matters for the new cable question.

Show the answer

Hint: a node has one edge if it is at the end of the chain.

Answer: two nodes, {0, 1, 2} and {6}. Node {3, 4, 5} has two edges. The count matters because each end of the tree is a block that needs an extra connection before the tree has no bridges. Check the claim on your own input before you rely on it, as the lesson says.

Problem 5: a test that catches the root rule

Write a 4-vertex input where vertex 0 is a leaf (one edge) and the rest form a triangle with vertex 1. Predict which vertices are cut vertices, then run the program and compare. Explain what the answer would be if the root rule were missing and the search started at 0.

Show the answer

Hint: vertex 0 is a leaf, so removing it cannot disconnect anything. Think about what the search does when it starts at 0.

Answer: the input 4 4 / 0 1 / 1 2 / 2 3 / 3 1 (file tri_leaf.txt) has a single edge from 0 to 1 and a triangle on 1, 2, 3. Vertex 1 is the only cut vertex, and the edge 0 to 1 is the only bridge. Real output of the correct program:

bridges: 0(0-1)
articulation points: 1

Vertex 0 is not a cut vertex, because it has one child in the DFS tree. Without the root rule, the search starting at 0 marks 0 as a cut vertex. The variant with the root rule removed prints articulation points: 0 1. The entry times depend on the edge order, so check the output on your machine.