SyntaxPilot
Courses/Competitive Programming/Lesson 50
Video coming soonThis lesson’s video is being made

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

Competitive Programming · Lesson 50 of 90

Bridges, articulation points and 2-edge-connected components

queued

These are the notes for Competitive Programming episode 50, the sixth episode of the graphs section. Roads go both ways again, and we ask which ones are fragile. Fragile Roads asks for every road whose closing splits the city: closing each road in turn and running a BFS is right on the sample but Time Limit Exceeded on a ring of 2 · 10^5 roads. An explorer who writes down his arrival time at each junction (tin) and asks every branch how far up it can climb back through a shortcut (low) finds every bridge in one DFS: road v–u is a bridge exactly when low[u] > tin[v]. Skipping the parent junction instead of the parent road prints 1 2 as a bridge when two parallel roads join 1 and 2; skipping the road by its id is accepted. Substations asks for the junctions whose closing splits the city (articulation points): the rule becomes low[u] >= tin[v], and applying it to the DFS root prints 1 3 4 where 3 4 is right; the root is a cut point only when it has two or more DFS children. Backup Routes answers "do a and b stay connected whichever single road closes?": "same component" says YES for 1 and 4, which are joined only through a bridge; deleting the bridges and painting the pieces (the 2-edge-connected components) is accepted. Three stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

An explorer maps a city by walking it depth first: from each junction he takes a road to a junction he has never seen, and only when every road from here leads somewhere already visited does he walk back. He carries a notebook. At each new junction he writes his arrival time: 1, 2, 3, ... When he sees a road leading back to a junction he visited earlier, he does not take it, but he notes "from here I could jump back up to time 3". When he finishes a branch and walks back, the branch hands him a report: the earliest arrival time anyone in this branch can climb back to using those shortcuts.

If the branch below a junction cannot climb back above that junction's parent, then the road he walked in on is the only link between the branch and the rest of the city. Close it, and the city splits. That road is fragile. One walk, one notebook, every fragile road.

Problem R1 · Fragile Roads

(Written for this course, in the style of a Codeforces Div. 2 E problem.)

A city has n junctions and m two-way roads; road i joins a_i and b_i (a_i ≠ b_i). Two roads may join the same pair of junctions. A road is fragile if closing it (and only it) leaves no way from a_i to b_i. Print how many roads are fragile, then each fragile road as a b with a < b, sorted.

  • Input: n and m (1 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a_i b_i. The city need not be connected.
  • Output: the number k of fragile roads, then k lines a b.
Input Output
7 8 / 1 2 / 2 3 / 3 1 / 3 4 / 4 5 / 5 6 / 6 4 / 6 7 2 / 3 4 / 6 7
3 3 / 1 2 / 1 2 / 2 3 1 / 2 3 (two roads join 1 and 2)
4 2 / 1 2 / 3 4 2 / 1 2 / 3 4 (two separate parts)

The first city is two triangles, 1–2–3 and 4–5–6, joined by the road 3–4, with a dead-end road 6–7. A fragile road is called a bridge. A road is a bridge exactly when it lies on no cycle: a cycle through it would give a second way around.

The obvious attempt: close each road and search (TLE)

For every road, pretend it is closed, run a BFS from one end, and check whether the other end is still reachable. The adjacency list stores (neighbour, road id) so that one road can be banned by its id.

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

int n, m;
vector<vector<pair<int, int>>> g;

bool reach(int s, int t, int banned) {      // BFS without road "banned"
    vector<bool> seen(n + 1, false);
    queue<int> q;
    q.push(s);
    seen[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto [u, id] : g[v])
            if (id != banned && !seen[u]) { seen[u] = true; q.push(u); }
    }
    return seen[t];
}
int main() {
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    vector<pair<int, int>> ans;
    for (int v = 1; v <= n; v++)
        for (auto [u, id] : g[v])
            if (v < u && !reach(v, u, id)) ans.push_back({v, u});   // close road id
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (auto [a, b] : ans) cout << a << " " << b << "\n";
}
2
3 4
6 7

Correct. Now one big ring of 2 · 10^5 junctions and 2 · 10^5 roads, built inside the program:

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

int n, m;
vector<vector<pair<int, int>>> g;

bool reach(int s, int t, int banned) {      // BFS without road "banned"
    vector<bool> seen(n + 1, false);
    queue<int> q;
    q.push(s);
    seen[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto [u, id] : g[v])
            if (id != banned && !seen[u]) { seen[u] = true; q.push(u); }
    }
    return seen[t];
}
int main() {
    n = 200000, m = 200000;                 // one big ring, built here
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a = i + 1, b = i + 1 < n ? i + 2 : 1;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    vector<pair<int, int>> ans;
    for (int v = 1; v <= n; v++)
        for (auto [u, id] : g[v])
            if (v < u && !reach(v, u, id)) ans.push_back({v, u});   // close road id
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (auto [a, b] : ans) cout << a << " " << b << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)

There are m = 2 · 10^5 roads, and each BFS walks the whole ring of 2 · 10^5 junctions: 2 · 10^5 × 2 · 10^5 = 4 · 10^10 junction visits, before even counting the roads it scans. (A ring has no bridges at all, so every BFS has to go all the way round.) We need one pass over the graph, not one per road.

The explorer's notebook: tin and low

Run one DFS. The roads the DFS walks down form the DFS tree: these are the tree edges, and the junction a tree edge comes from is the parent. Every other road joins a junction to one of its ancestors in the tree (in an undirected DFS there are no "cross" roads between separate branches); these are the back edges, the explorer's shortcuts.

  • tin[v]: the arrival time of v, ++timer when the DFS first enters v.
  • low[v]: the smallest tin that v's whole subtree can reach using tree edges downward and at most one back edge upward. It starts as tin[v], takes tin[u] for every back edge v–u, and takes low[u] from every DFS child u.

The bridge rule. A back edge can only lead to an ancestor, so if the subtree of child u has a back edge to v or above, the road v–u lies on a cycle. Otherwise nothing in u's subtree touches anything outside it except through v–u. So the tree edge v–u is a bridge exactly when

low[u] > tin[v]

A back edge is never a bridge: it closes a cycle with the tree path.

The sample, starting at junction 1 (neighbours in input order):

Junction tin low Why low Road from parent low[child] > tin[parent]?
1 1 1 itself (root) none
2 2 1 from child 3 1–2 1 > 1? no
3 3 1 back edge 3–1 2–3 1 > 2? no
4 4 4 back edge 6–4 reaches only 4 3–4 4 > 3? yes: bridge
5 5 4 from child 6 4–5 4 > 4? no
6 6 4 back edge 6–4 5–6 4 > 5? no
7 7 7 no shortcut at all 6–7 7 > 6? yes: bridge

Two bridges, 3–4 and 6–7, as the brute force said. This is Tarjan's low-link idea, and it costs one DFS: O(n + m).

The natural code: skip the parent junction (WA)

To avoid treating the road we came in by as a shortcut, the first version remembers the junction we came from, p, and skips it:

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<pair<int, int>> br;   // bridges

void dfs(int v, int p) {                    // p = the junction we came from
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (u == p) continue;                // don't walk straight back
        if (tin[u]) low[v] = min(low[v], tin[u]);     // shortcut up the tree
        else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) br.push_back({min(u, v), max(u, v)});
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    sort(br.begin(), br.end());
    cout << br.size() << "\n";
    for (auto [a, b] : br) cout << a << " " << b << "\n";
}

On the sample:

2
3 4
6 7

On the city with two parallel roads between 1 and 2:

2
1 2
2 3

Wrong Answer: the expected output is 1 / 2 3. There are two roads between 1 and 2, so closing one leaves the other. When the DFS stands at 2 with parent 1, if (u == p) continue; skips both roads to 1, so the second road is never seen as the shortcut it is, and low[2] stays 2 > tin[1] = 1.

The fix: skip the parent road by its id

Remember the road id we came in by, pe, and skip only that road. A second road to the parent is then an ordinary back edge.

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<pair<int, int>> br;   // bridges

void dfs(int v, int pe) {                   // pe = the ROAD we came in by
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;              // skip only that road
        if (tin[u]) low[v] = min(low[v], tin[u]);     // shortcut up the tree
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) br.push_back({min(u, v), max(u, v)});
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    sort(br.begin(), br.end());
    cout << br.size() << "\n";
    for (auto [a, b] : br) cout << a << " " << b << "\n";
}

The parallel roads, the sample, and the city in two separate parts:

1
2 3
2
3 4
6 7
2
1 2
3 4

The loop for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1); starts a new DFS in every part of the city, so a disconnected input is handled.

The worst case

10^5 junctions and 2 · 10^5 roads, built inside the program: first a random tree (every road of it is a bridge on its own), then 10^5 more roads thrown among junctions 1 … 2000, which puts that corner of the tree on cycles.

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<pair<int, int>> br;   // bridges

void dfs(int v, int pe) {                   // pe = the ROAD we came in by
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;              // skip only that road
        if (tin[u]) low[v] = min(low[v], tin[u]);     // shortcut up the tree
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) br.push_back({min(u, v), max(u, v)});
        }
    }
}
int main() {
    n = 100000, m = 200000;                 // worst case, built here
    mt19937 rng(50);
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a = i + 2, b = rng() % (i + 1) + 1;   // first a random tree
        if (i >= n - 1) a = rng() % 2000 + 1, b = rng() % 2000 + 1;   // then a tangle
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    cout << br.size() << " bridges\n";
}
98000 bridges

0.03 seconds. (A random tree is shallow, so the recursion stays short here; see "Recursion depth" below for the case where it does not.)

Stress test against closing every road

500 tiny random cities, with parallel roads and separate parts allowed, checked against the brute force:

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<pair<int, int>> br;   // bridges

void dfs(int v, int pe) {                   // pe = the ROAD we came in by
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;              // skip only that road
        if (tin[u]) low[v] = min(low[v], tin[u]);     // shortcut up the tree
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) br.push_back({min(u, v), max(u, v)});
        }
    }
}
bool reach(int s, int t, int banned) {
    vector<bool> seen(n + 1, false);
    vector<int> st = {s};
    seen[s] = true;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, id] : g[v])
            if (id != banned && !seen[u]) seen[u] = true, st.push_back(u);
    }
    return seen[t];
}
int main() {
    mt19937 rng(50);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 7 + 1, m = rng() % 10;
        g.assign(n + 1, {});
        for (int i = 0; i < m; i++) {
            int a = rng() % n + 1, b = rng() % n + 1;
            if (a == b) { i--, m--; continue; }   // no self-loops
            g[a].push_back({b, i});
            g[b].push_back({a, i});
        }
        timer = 0;
        br.clear();
        tin.assign(n + 1, 0);
        low.assign(n + 1, 0);
        for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
        vector<pair<int, int>> slow;
        for (int v = 1; v <= n; v++)
            for (auto [u, id] : g[v])
                if (v < u && !reach(v, u, id)) slow.push_back({v, u});
        sort(br.begin(), br.end());
        sort(slow.begin(), slow.end());
        if (br != slow) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem R2 · Substations

(Written for this course.)

The same city. Now a junction can close (a power substation going down), and all its roads close with it. A junction is critical if closing it leaves the remaining junctions in more connected pieces than before. Print how many junctions are critical, then the critical junctions in increasing order on one line.

  • Input: as in Fragile Roads (n, m ≤ 2 · 10^5, a_i ≠ b_i, parallel roads allowed).
  • Output: the count, then the junctions separated by spaces.
Input Output
5 5 / 1 2 / 2 3 / 3 1 / 3 4 / 4 5 2 / 3 4
3 2 / 2 1 / 1 3 1 / 1

Such a junction is an articulation point (or cut point, cut vertex).

Same notebook, ≥ instead of >

For a non-root junction v with DFS child u: if u's subtree cannot climb above v, then once v is closed that subtree is cut off from v's parent. So v is a cut point when some child u has

low[u] >= tin[v]

Greater or equal this time. For a bridge, a subtree that climbs back exactly to v is fine: v is still there, and the road v–u is on a cycle through v. For a cut point, climbing back to v itself does not help, because v is the junction that closed.

The child rule everywhere (WA at the root)

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<bool> cut;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] >= tin[v]) cut[v] = true;   // u's branch can't climb above v
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    cut.assign(n + 1, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    vector<int> ans;
    for (int v = 1; v <= n; v++) if (cut[v]) ans.push_back(v);
    cout << ans.size() << "\n";
    for (int v : ans) cout << v << " ";
}

The triangle 1–2–3 with the tail 3–4–5:

3
1 3 4

Wrong Answer: the expected output is 2 / 3 4. Closing junction 1 leaves 2 and 3 joined directly. Junction 1 is where the DFS started.

The root rule

The root has the smallest tin, so nothing can climb above it, and low[u] >= tin[root] is true for every child: the rule tells us nothing. Look at the DFS children instead:

  • one DFS child: the whole rest of the city is that child's subtree, which stays connected without the root. Not a cut point.
  • two or more DFS children: the DFS could not get from the first child's subtree to the second without going back through the root (otherwise the second child would have been visited inside the first subtree). They meet only through the root: a cut point.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<bool> cut;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    int kids = 0;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            kids++;
            low[v] = min(low[v], low[u]);
            if (pe != -1 && low[u] >= tin[v]) cut[v] = true;   // not for the root
        }
    }
    if (pe == -1 && kids > 1) cut[v] = true;   // root: two or more DFS children
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    cut.assign(n + 1, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    vector<int> ans;
    for (int v = 1; v <= n; v++) if (cut[v]) ans.push_back(v);
    cout << ans.size() << "\n";
    for (int v : ans) cout << v << " ";
}
2
3 4

And a root in the middle, roads 2–1 and 1–3 (junction 1 has two DFS children):

1
1

Stress test: close each junction and count the pieces

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<bool> cut;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    int kids = 0;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            kids++;
            low[v] = min(low[v], low[u]);
            if (pe != -1 && low[u] >= tin[v]) cut[v] = true;   // not for the root
        }
    }
    if (pe == -1 && kids > 1) cut[v] = true;   // root: two or more DFS children
}
int pieces(int banned) {                     // components with junction "banned" closed
    vector<bool> seen(n + 1, false);
    int c = 0;
    for (int s = 1; s <= n; s++) {
        if (s == banned || seen[s]) continue;
        c++;
        vector<int> st = {s};
        seen[s] = true;
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            for (auto [u, id] : g[v])
                if (u != banned && !seen[u]) seen[u] = true, st.push_back(u);
        }
    }
    return c;
}
int main() {
    mt19937 rng(50);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 7 + 1, m = rng() % 10;
        g.assign(n + 1, {});
        for (int i = 0; i < m; i++) {
            int a = rng() % n + 1, b = rng() % n + 1;
            if (a == b) { i--, m--; continue; }
            g[a].push_back({b, i});
            g[b].push_back({a, i});
        }
        timer = 0;
        tin.assign(n + 1, 0);
        low.assign(n + 1, 0);
        cut.assign(n + 1, false);
        for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
        int base = pieces(0);
        for (int v = 1; v <= n; v++)
            if (cut[v] != (pieces(v) > base)) {
                cout << "mismatch on test " << t;
                return 0;
            }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem R3 · Backup Routes

(Written for this course, in the style of an AtCoder Beginner Contest F problem.)

The same city, and q questions. Question j names two junctions a_j and b_j. Answer YES if a_j and b_j stay connected whichever single road closes (an ambulance wants a backup route), otherwise NO. A junction with itself is always YES.

  • Input: n and m (n, m ≤ 2 · 10^5), m roads as before, then q (q ≤ 2 · 10^5) and q lines a_j b_j.
  • Output: q lines, YES or NO.
Input Output
the 7-junction city of Fragile Roads, then 5 / 1 3 / 1 4 / 4 6 / 6 7 / 5 5 YES / NO / YES / NO / YES

The obvious attempt: same connected component (WA)

A DSU joins the two ends of every road; each question checks whether a and b are in the same group.

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

int n, m;
vector<vector<pair<int, int>>> g;

struct DSU {
    vector<int> p;
    DSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) { p[find(a)] = find(b); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    DSU d(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
        d.unite(a, b);
    }
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n";   // same component?
    }
}
YES
YES
YES
YES
YES

Wrong Answer at the second question: 1 and 4 are connected, but only through the bridge 3–4. Close it and the ambulance is stuck. The same goes for 6 and 7. Connected is not the same as backed up.

Delete the bridges, then paint

Mark every bridge with the low-link DFS (by road id, so parallel roads are handled). Then flood fill from each unpainted junction, never crossing a bridge. Each colour is a 2-edge-connected component: a maximal group of junctions that stay connected after removing any one road.

Why it is correct. If a and b get the same colour, they are joined by a path of non-bridge roads; each such road lies on a cycle, so if one of them closes, the path can detour around that cycle, and closing a bridge does not touch the path at all. If a and b get different colours (and are connected), every path between them must cross some bridge (that is what stopped the paint), and a bridge is the only link between its two sides, so closing it separates them. So each question is one comparison, comp[a] == comp[b], and the different-part case is NO automatically.

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, comp;
vector<bool> isBridge;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) isBridge[id] = true;
        }
    }
}
void paint(int v, int c) {                  // flood fill, never across a bridge
    comp[v] = c;
    for (auto [u, id] : g[v])
        if (!isBridge[id] && !comp[u]) paint(u, c);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    comp.assign(n + 1, 0);
    isBridge.assign(m, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    int c = 0;
    for (int v = 1; v <= n; v++) if (!comp[v]) paint(v, ++c);
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (comp[a] == comp[b] ? "YES" : "NO") << "\n";
    }
}
YES
NO
YES
NO
YES

1 and 4 are separated by the bridge 3–4, and 6 and 7 by the bridge 6–7. The worst case: 10^5 junctions, 2 · 10^5 roads, 2 · 10^5 random questions.

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, comp;
vector<bool> isBridge;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) isBridge[id] = true;
        }
    }
}
void paint(int v, int c) {                  // flood fill, never across a bridge
    comp[v] = c;
    for (auto [u, id] : g[v])
        if (!isBridge[id] && !comp[u]) paint(u, c);
}
int main() {
    n = 100000, m = 200000;                 // worst case, built here
    mt19937 rng(50);
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a = i + 2, b = rng() % (i + 1) + 1;   // first a random tree
        if (i >= n - 1) a = rng() % 2000 + 1, b = rng() % 2000 + 1;   // then a tangle
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    comp.assign(n + 1, 0);
    isBridge.assign(m, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    int c = 0;
    for (int v = 1; v <= n; v++) if (!comp[v]) paint(v, ++c);
    int same = 0;
    for (int i = 0; i < 200000; i++) same += comp[rng() % n + 1] == comp[rng() % n + 1];
    cout << c << " pieces, " << same << " YES of 200000\n";
}
98001 pieces, 79 YES of 200000

0.03 seconds. 98 000 bridges cut the city into 98 001 pieces: the tangled corner around junctions 1 … 2000, and almost every other junction alone. A random pair is rarely in the same piece, hence only 79 YES.

Stress test: close every road for every pair

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, comp;
vector<bool> isBridge;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) isBridge[id] = true;
        }
    }
}
void paint(int v, int c) {                  // flood fill, never across a bridge
    comp[v] = c;
    for (auto [u, id] : g[v])
        if (!isBridge[id] && !comp[u]) paint(u, c);
}
bool reach(int s, int t, int banned) {
    vector<bool> seen(n + 1, false);
    vector<int> st = {s};
    seen[s] = true;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, id] : g[v])
            if (id != banned && !seen[u]) seen[u] = true, st.push_back(u);
    }
    return seen[t];
}
int main() {
    mt19937 rng(50);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 7 + 1, m = rng() % 10;
        g.assign(n + 1, {});
        for (int i = 0; i < m; i++) {
            int a = rng() % n + 1, b = rng() % n + 1;
            if (a == b) { i--, m--; continue; }
            g[a].push_back({b, i});
            g[b].push_back({a, i});
        }
        timer = 0;
        tin.assign(n + 1, 0);
        low.assign(n + 1, 0);
        comp.assign(n + 1, 0);
        isBridge.assign(m, false);
        for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
        int c = 0;
        for (int v = 1; v <= n; v++) if (!comp[v]) paint(v, ++c);
        for (int a = 1; a <= n; a++)
            for (int b = 1; b <= n; b++) {
                bool ok = reach(a, b, -1);           // try closing every road
                for (int r = 0; r < m; r++) ok = ok && reach(a, b, r);
                if (ok != (comp[a] == comp[b])) {
                    cout << "mismatch on test " << t;
                    return 0;
                }
            }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Memory Verdict
close each road + BFS O(m · (n + m)) O(n + m) TLE: 4 · 10^10 steps on the 2 · 10^5 ring
low-link DFS for bridges O(n + m) O(n + m) accepted, 0.03 s for n = 10^5, m = 2 · 10^5
close each junction + search O(n · (n + m)) O(n + m) only for the stress test
low-link DFS for cut points O(n + m) O(n + m) accepted (same DFS, one counter)
same component (DSU) for backup routes O((m + q) α(n)) O(n) fast but Wrong Answer
bridges + paint + compare colours O(n + m + q) O(n + m) accepted, 0.03 s with q = 2 · 10^5

Common mistakes (and the real outputs)

Mistake What you see Why Fix
close each road and search Time Limit Exceeded m BFS runs of O(n + m) one low-link DFS
skip the parent junction 2 / 1 2 / 2 3 (expected 1 / 2 3) a parallel road to the parent is a real cycle skip the parent road id pe
child rule on the root 3 / 1 3 4 (expected 2 / 3 4) nothing is above the root, so low >= tin is always true root: cut point only if kids > 1
> for cut points 2 / 3 6 on the Fragile Roads city (expected 3 / 3 4 6) junction 4's branch climbs back exactly to 4, and that does not help once 4 is closed >= for points, > for bridges
>= for bridges 4 / 1 2 / 3 4 / 4 5 / 6 7 (expected 2 / 3 4 / 6 7) climbing back to v keeps v–u on a cycle > for bridges
same component = backup route YES for 1 4 (expected NO) a bridge lies between them 2-edge-connected components
only dfs(1, -1) 1 / 1 2 on the two-part city (expected 2 / 1 2 / 3 4) the city need not be connected loop over every unvisited junction
recursive DFS on a 10^5-long path Segmentation fault (Runtime Error) the call stack is 8 MB iterative DFS, or a bigger stack

Recursion depth: a deep DFS can crash

Every call of dfs keeps a stack frame (its arguments, the loop iterator, saved registers) until it returns, so the recursion is as deep as the DFS tree. On a city that is one long path, that is n calls deep. Here is the accepted Fragile Roads DFS on a path of 10^5 junctions, built inside the program:

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<pair<int, int>> br;   // bridges

void dfs(int v, int pe) {                   // pe = the ROAD we came in by
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;              // skip only that road
        if (tin[u]) low[v] = min(low[v], tin[u]);     // shortcut up the tree
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) br.push_back({min(u, v), max(u, v)});
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = 100000, m = n - 1;                  // one long path, built here
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        g[i + 1].push_back({i + 2, i});
        g[i + 2].push_back({i + 1, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    cout << br.size() << " bridges\n";
}

Run with the usual Linux limit of 8 MB of stack (ulimit -s prints 8192):

Segmentation fault (exit code 139)

On a judge this is Runtime Error (signal SIGSEGV, a stack overflow). The same thing happens to the episode's TARJAN on a path of 2 · 10^5 junctions, which the constraints of Fragile Roads allow. With an unlimited stack (ulimit -s unlimited before running) the same program prints:

99999 bridges

How to avoid it:

  • Iterative DFS (always safe): keep your own stack of junctions and, for each junction, the index of the next road to look at. "Calling" dfs(u) is pushing u; "returning" is popping v and updating its parent's low. Practice problem 4 below is exactly this, and the Java and Python solutions at the end use it.
  • A bigger stack, on judges that allow it: some judges already give a large stack (Codeforces does), and locally on Linux you can run ulimit -s unlimited. You cannot rely on this everywhere, so on a judge with an 8 MB stack and n = 10^5 or more, write the iterative version.
  • In Python the default recursion limit is 1000, and raising it with sys.setrecursionlimit only moves the problem: the interpreter's own stack can then overflow and crash. In Java, deep recursion on the default thread stack ends in StackOverflowError. Use the iterative DFS in both.

The paint flood fill of Backup Routes is recursive as well, and on a long path it is just as deep (the episode's TWO crashes the same way on a path of 2 · 10^5 junctions), so the iterative solutions paint with an explicit stack.

Mini project

Write a graph fragility report. Read a city, then print: the bridges, the cut points, the 2-edge-connected components with their sizes, and the bridge tree (practice problem 3). Add a mode that reads a road map as an ASCII grid (# = road cell, junctions where roads meet) and draws the bridges with = and the cut points with X. Implement the DFS twice, recursively and iteratively, and check on 1000 random cities that both give the same answers; then time both on a path of 10^6 junctions with ulimit -s unlimited for the recursive one. Finally, add the brute forces from the stress tests and run all three stress tests from one program.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).

1. Add one road to remove the most bridges. The city is connected. You may build one new road between any two junctions. Print the largest number of bridges that stop being bridges.

Solution

Shrink every 2-edge-connected component into one node: the bridges then form a tree (the bridge tree). A new road between junctions in components X and Y closes a cycle through every bridge on the tree path from X to Y, and only those, so they stop being bridges. The best choice is the longest path in the tree: its diameter, found with two BFS runs (BFS from any node, then BFS from the farthest node found).

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, comp;
vector<bool> isBridge;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) isBridge[id] = true;
        }
    }
}
void paint(int v, int c) {
    comp[v] = c;
    for (auto [u, id] : g[v])
        if (!isBridge[id] && !comp[u]) paint(u, c);
}
pair<int, int> farthest(int s, vector<vector<int>> &t) {   // BFS in the bridge tree: (node, distance)
    vector<int> d(t.size(), -1);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    int best = s;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (d[v] > d[best]) best = v;
        for (int u : t[v]) if (d[u] < 0) { d[u] = d[v] + 1; q.push(u); }
    }
    return {best, d[best]};
}
int main() {
    cin >> n >> m;                          // the city is connected
    g.assign(n + 1, {});
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; i++) {
        auto &[a, b] = e[i];
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    comp.assign(n + 1, 0);
    isBridge.assign(m, false);
    dfs(1, -1);
    int c = 0;
    for (int v = 1; v <= n; v++) if (!comp[v]) paint(v, ++c);
    vector<vector<int>> t(c + 1);           // the bridge tree
    for (int i = 0; i < m; i++)
        if (isBridge[i]) {
            t[comp[e[i].first]].push_back(comp[e[i].second]);
            t[comp[e[i].second]].push_back(comp[e[i].first]);
        }
    int far = farthest(1, t).first;         // two BFS runs give the diameter
    cout << farthest(far, t).second << "\n";   // bridges on the longest tree path
}

The Fragile Roads sample (one road from 1 to 7 fixes both bridges), the tree 6 5 / 1 2 / 2 3 / 3 4 / 2 5 / 5 6 (a road from 4 to 6 fixes 4 of the 5 bridges) and the Substations sample:

2
4
2

2. Count pairs cut by each cut point. The city is connected. For every junction v, print how many unordered pairs of other junctions {a, b} can no longer reach each other when v closes (0 for a junction that is not a cut point).

Solution

During the DFS keep the subtree size sz[u]. When v closes, every child u with low[u] >= tin[v] falls off as a piece of size sz[u]; everything else (the part above v and the children that climb above v) stays together, n − 1 − (sum of those sizes) junctions. For the root every child is a piece and nothing is "above", which is exactly the root rule. If the pieces have sizes s_1, s_2, ..., the separated pairs are (Σ s_i · (n − 1 − s_i)) / 2. Use long long: up to about 2 · 10^10 pairs.

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, sz;
vector<ll> pairsCut;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    sz[v] = 1;
    vector<ll> pieces;                      // sizes of the parts left when v closes
    ll sep = 0;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            sz[v] += sz[u];
            low[v] = min(low[v], low[u]);
            if (low[u] >= tin[v]) { pieces.push_back(sz[u]); sep += sz[u]; }   // u's branch falls off
        }
    }
    if (n - 1 - sep > 0) pieces.push_back(n - 1 - sep);   // everything else stays together
    ll s = 0;
    for (ll p : pieces) s += p * (n - 1 - p);
    pairsCut[v] = s / 2;                    // pairs in different pieces
}
int main() {
    cin >> n >> m;                          // the city is connected
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    sz.assign(n + 1, 0);
    pairsCut.assign(n + 1, 0);
    dfs(1, -1);
    for (int v = 1; v <= n; v++) cout << pairsCut[v] << " \n"[v == n];
}

The Substations samples and the Fragile Roads sample (closing 3 separates {1, 2} from {4, 5, 6, 7}: 8 pairs; closing 4 separates {1, 2, 3} from {5, 6, 7}: 9 pairs):

0 0 4 3 0
1 0 0
0 0 8 9 0 5 0

3. Build the bridge tree. Print the number of 2-edge-connected components k, then the component of every junction, then one line x y (x < y, sorted) per bridge, joining the components of its two ends.

Solution

Find the bridges, paint without crossing them, and turn each bridge into an edge between the two colours. If the city is connected the result is a tree with k − 1 edges (otherwise a forest). Many problems become easy on this tree: "how many bridges between a and b" is a tree distance, homework 1 is its diameter, and "a road that must be used by every route from a to b" is a bridge on the tree path.

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, comp;
vector<bool> isBridge;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) isBridge[id] = true;
        }
    }
}
void paint(int v, int c) {
    comp[v] = c;
    for (auto [u, id] : g[v])
        if (!isBridge[id] && !comp[u]) paint(u, c);
}
int main() {
    cin >> n >> m;
    g.assign(n + 1, {});
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; i++) {
        auto &[a, b] = e[i];
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    comp.assign(n + 1, 0);
    isBridge.assign(m, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    int c = 0;
    for (int v = 1; v <= n; v++) if (!comp[v]) paint(v, ++c);
    vector<pair<int, int>> tree;            // one tree edge per bridge
    for (int i = 0; i < m; i++)
        if (isBridge[i]) {
            int x = comp[e[i].first], y = comp[e[i].second];
            tree.push_back({min(x, y), max(x, y)});
        }
    sort(tree.begin(), tree.end());
    cout << c << "\n";
    for (int v = 1; v <= n; v++) cout << comp[v] << " \n"[v == n];
    for (auto [x, y] : tree) cout << x << " " << y << "\n";
}

The Fragile Roads sample, then the Substations sample:

3
1 1 1 2 2 2 3
1 2
2 3
3
1 1 1 2 3
1 2
2 3

4. Iterative DFS low-link for a 10^6 path. Count the bridges of a city with up to 10^6 junctions and roads, on a judge with an 8 MB stack, when the city may be one long path.

Solution

Replace the recursion by an explicit stack. For each junction keep it[v], the index of the next road to look at, pe[v] (the road id it came in by) and par[v]. While the stack is not empty, look at its top v: if v has another road, handle it exactly like the loop body of dfs (an unvisited u is "called" by setting its tin and pushing it); if not, pop v ("return") and do what the recursive version did after dfs(u, id) came back: update low[par[v]] and test the bridge rule.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    vector<int> tin(n + 1, 0), low(n + 1, 0), pe(n + 1, -1), par(n + 1, 0), it(n + 1, 0);
    int timer = 0, bridges = 0;
    vector<int> st;                         // our own stack instead of recursion
    for (int s = 1; s <= n; s++) {
        if (tin[s]) continue;
        tin[s] = low[s] = ++timer;
        st.push_back(s);
        while (!st.empty()) {
            int v = st.back();
            if (it[v] < (int)g[v].size()) {          // next road of v
                auto [u, id] = g[v][it[v]++];
                if (id == pe[v]) continue;
                if (tin[u]) low[v] = min(low[v], tin[u]);
                else {                                // "call" dfs(u, id)
                    tin[u] = low[u] = ++timer;
                    pe[u] = id;
                    par[u] = v;
                    st.push_back(u);
                }
            } else {                                  // "return" from v
                st.pop_back();
                if (pe[v] != -1) {
                    int p = par[v];
                    low[p] = min(low[p], low[v]);
                    if (low[v] > tin[p]) bridges++;
                }
            }
        }
    }
    cout << bridges << "\n";
}

The Fragile Roads sample, the parallel-road city, and a path of 10^6 junctions read from the input (run with the default 8 MB stack, 0.16 s):

2
1
999999

The recursive version crashes on the same path with Segmentation fault.

Quick quiz

A connected city with 6 junctions and 5 roads (so it is a tree). How many bridges?

if (low[u] > tin[v]) bridge;

A) 0 · B) 1 · C) 5 · D) 6

Answer

C. A tree has no cycles, so every one of its n − 1 = 5 roads is the only link between its two sides: every road is a bridge. (In the DFS, no junction has a back edge, so low[u] = tin[u] > tin[v] for every tree edge.)

Interview questions

  1. What is a bridge, and how do you find all of them? An edge whose removal increases the number of connected components; equivalently, an edge on no cycle. One DFS computes tin and low; tree edge v–u is a bridge iff low[u] > tin[v]. O(n + m).
  2. What is low[v]? The smallest entry time reachable from v's DFS subtree using tree edges down and at most one back edge up.
  3. What is an articulation point, and how is the rule different? A vertex whose removal increases the number of components. A non-root v is one iff some child u has low[u] ≥ tin[v]; the root is one iff it has at least two DFS children.
  4. Why does the root need a special rule? Nothing has a smaller tin than the root, so low[u] ≥ tin[root] holds for every child and says nothing; the root separates its children only when there are at least two of them.
  5. How do you handle multi-edges? Skip the edge you entered by (by edge id), not every edge to the parent vertex; a second parallel edge is a back edge, so neither copy is a bridge.
  6. What is a 2-edge-connected component, and how do you compute it? A maximal set of vertices that stay connected after removing any one edge. Remove the bridges and take connected components; shrinking each to a node gives the bridge tree.
  7. What changes for very large n? The recursion depth can reach n; use an iterative DFS (or a larger stack where allowed) to avoid a stack overflow.

Glossary

Term Meaning Example
Junction / road A node / an undirected edge of the city graph 7 junctions, 8 roads
Bridge (fragile road) An edge whose removal disconnects its two ends; an edge on no cycle 3–4 and 6–7
Articulation point (cut point, cut vertex) A node whose removal splits the rest of the graph into more pieces junctions 3 and 4 in the Substations sample
Cycle A path that returns to its start without reusing a road 1–2–3–1
Parallel roads (multi-edges) Two or more roads joining the same pair of junctions two roads 1–2
Self-loop A road from a junction to itself (excluded here) 5–5
Connected component A maximal group of junctions that can reach each other {1, 2} and {3, 4}
DFS (depth-first search) Go as deep as possible, back up only when stuck the explorer's walk
DFS tree The roads the DFS walks down, forming a tree (a forest if disconnected) 1–2–3–4–5–6–7
Tree edge A road the DFS used to reach a new junction 2–3
Back edge A non-tree road from a junction to one of its ancestors 3–1, 6–4
Root The junction where a DFS starts junction 1
Parent / child The two ends of a tree edge, the upper and the lower one 3 is the parent of 4
Subtree (branch) A junction and everything the DFS reached below it {4, 5, 6, 7}
tin (entry time) The time stamp ++timer when the DFS first enters a junction tin[4] = 4
low / low-link The smallest tin reachable from a subtree with at most one back edge low[6] = 4
Bridge rule Tree edge v–u is a bridge iff low[u] > tin[v] 4 > 3 for 3–4
Cut point rule Non-root v is a cut point iff some child has low[u] ≥ tin[v] low[4] = 4 ≥ tin[3] = 3
Root rule The root is a cut point iff it has two or more DFS children root 1 of 2 1 / 1 3
pe (parent edge id) The id of the road the DFS came in by, skipped instead of the parent junction if (id == pe) continue;
Tarjan's low-link The tin/low technique (Robert Tarjan, 1970s) this whole episode
2-edge-connected component A maximal group that stays connected after removing any one road; what remains after deleting bridges {1, 2, 3}, {4, 5, 6}, {7}
Bridge tree The tree whose nodes are 2-edge-connected components and whose edges are the bridges 1 – 2 – 3
Tree diameter The longest path in a tree 4 in homework 1
Flood fill (paint) Give a colour to everything reachable from a start, here without crossing bridges paint(v, c)
DSU (union–find) Keeps groups of nodes under unite, answers "same group?" the WA "same component" attempt
BFS Breadth-first search, used by the brute force reach(s, t, banned)
Recursion depth How many calls are active at once; for a DFS, the depth of the DFS tree 10^5 on a path
Stack overflow The call stack (8 MB by default on Linux) runs out; the program dies with SIGSEGV Segmentation fault
SIGSEGV / Runtime Error (RE) The signal for an invalid memory access / the judge's verdict for a crash deep recursion
Iterative DFS A DFS with an explicit stack instead of recursion homework 4
ulimit -s The shell command that shows or sets the stack limit 8192 (KB)
O(n + m) Linear time: each junction and road handled a constant number of times one low-link DFS
Brute force Trying every possibility directly close each road and search
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Time Limit Exceeded (TLE) The program is too slow close each road on the ring
Wrong Answer (WA) The output is wrong 1 2 reported as a bridge
Accepted Correct and fast enough skip the road by id

Summary

  • A bridge is a road on no cycle; closing each road and searching is O(m · (n + m)): TLE.
  • One DFS stamps tin and computes low, the earliest tin a branch can climb back to; tree edge v–u is a bridge iff low[u] > tin[v]. O(n + m).
  • Skip the road id you came in by, not the parent junction: otherwise parallel roads give 1 2 as a bridge.
  • Cut points: low[u] ≥ tin[v] for non-root v; the root is a cut point only with two or more DFS children (otherwise 1 3 4 instead of 3 4).
  • Backup routes: delete the bridges and paint; same colour = same 2-edge-connected component = YES. "Same component" is WA.
  • The recursion is as deep as the DFS tree: a 10^5-long path crashes an 8 MB stack. Use an iterative DFS (or a bigger stack where the judge allows it).

Solutions in C++, Java and Python

Problem R1 · Fragile Roads

C++ (the episode's accepted code; recursive, so on a judge with an 8 MB stack and a long path use the iterative DFS of practice problem 4)

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<pair<int, int>> br;   // bridges

void dfs(int v, int pe) {                   // pe = the ROAD we came in by
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;              // skip only that road
        if (tin[u]) low[v] = min(low[v], tin[u]);     // shortcut up the tree
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) br.push_back({min(u, v), max(u, v)});
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    sort(br.begin(), br.end());
    cout << br.size() << "\n";
    for (auto [a, b] : br) cout << a << " " << b << "\n";
}
2
3 4
6 7
1
2 3
2
1 2
3 4

Java (iterative DFS over a flat adjacency array, byte-level fast input; 0.3 s on a path of 2 · 10^5 junctions with m = 2 · 10^5)

import java.io.*;
import java.util.*;

public class Main {
    static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
    static int nextInt() throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
    public static void main(String[] args) throws IOException {
        int n = nextInt(), m = nextInt();
        int[] ea = new int[m], eb = new int[m], start = new int[n + 2];
        for (int i = 0; i < m; i++) {
            ea[i] = nextInt(); eb[i] = nextInt();
            start[ea[i]]++; start[eb[i]]++;
        }
        for (int v = 1; v <= n + 1; v++) start[v] += start[v - 1];     // adjacency as one flat array
        int[] to = new int[2 * m], rid = new int[2 * m];
        for (int i = 0; i < m; i++) {
            int p = --start[ea[i]]; to[p] = eb[i]; rid[p] = i;
            p = --start[eb[i]]; to[p] = ea[i]; rid[p] = i;
        }
        int[] tin = new int[n + 1], low = new int[n + 1], pe = new int[n + 1], par = new int[n + 1], it = new int[n + 1];
        int[] stack = new int[n + 1];
        boolean[] isBridge = new boolean[m];
        int timer = 0, cnt = 0;
        for (int s = 1; s <= n; s++) {
            if (tin[s] != 0) continue;
            int top = 0;
            stack[top++] = s;
            tin[s] = low[s] = ++timer; pe[s] = -1; it[s] = start[s];
            while (top > 0) {                                  // iterative DFS: no recursion
                int v = stack[top - 1];
                if (it[v] < start[v + 1]) {
                    int u = to[it[v]], id = rid[it[v]];
                    it[v]++;
                    if (id == pe[v]) continue;                     // skip only the road we came in by
                    if (tin[u] != 0) low[v] = Math.min(low[v], tin[u]);
                    else {
                        tin[u] = low[u] = ++timer; pe[u] = id; par[u] = v; it[u] = start[u];
                        stack[top++] = u;
                    }
                } else {
                    top--;                                         // v is finished: report to its parent
                    if (pe[v] != -1) {
                        int p = par[v];
                        low[p] = Math.min(low[p], low[v]);
                        if (low[v] > tin[p]) { isBridge[pe[v]] = true; cnt++; }
                    }
                }
            }
        }
        long[] keys = new long[cnt];
        int k = 0;
        for (int i = 0; i < m; i++)
            if (isBridge[i]) keys[k++] = (long) Math.min(ea[i], eb[i]) * (n + 1) + Math.max(ea[i], eb[i]);
        Arrays.sort(keys);
        StringBuilder sb = new StringBuilder();
        sb.append(cnt).append('\n');
        for (long key : keys) sb.append(key / (n + 1)).append(' ').append(key % (n + 1)).append('\n');
        System.out.print(sb);
    }
}
2
3 4
6 7
1
2 3
2
1 2
3 4

Python (iterative DFS; each adj[v] is a flat list neighbour, road id, neighbour, road id, ...)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    ea = [int(x) for x in data[2:2 + 2 * m:2]]
    eb = [int(x) for x in data[3:3 + 2 * m:2]]
    adj = [[] for _ in range(n + 1)]          # adj[v] = flat list: neighbour, road id, neighbour, road id, ...
    for i in range(m):
        a, b = ea[i], eb[i]
        adj[a] += (b, i)
        adj[b] += (a, i)
    tin = [0] * (n + 1)
    low = [0] * (n + 1)
    pe = [-1] * (n + 1)
    par = [0] * (n + 1)
    it = [0] * (n + 1)
    bridges = []
    timer = 0
    for s in range(1, n + 1):
        if tin[s]:
            continue
        timer += 1
        tin[s] = low[s] = timer
        stack = [s]
        while stack:                          # iterative DFS: no recursion limit
            v = stack[-1]
            av = adj[v]
            if it[v] < len(av):
                u, rid = av[it[v]], av[it[v] + 1]
                it[v] += 2
                if rid == pe[v]:
                    continue                  # skip only the road we came in by
                if tin[u]:
                    if tin[u] < low[v]:
                        low[v] = tin[u]
                else:
                    timer += 1
                    tin[u] = low[u] = timer
                    pe[u] = rid
                    par[u] = v
                    stack.append(u)
            else:
                stack.pop()                   # v is finished: report to its parent
                if pe[v] != -1:
                    p = par[v]
                    if low[v] < low[p]:
                        low[p] = low[v]
                    if low[v] > tin[p]:
                        bridges.append((min(p, v), max(p, v)))
    bridges.sort()
    out = [str(len(bridges))] + [f"{a} {b}" for a, b in bridges]
    sys.stdout.write("\n".join(out) + "\n")

main()
2
3 4
6 7
1
2 3
2
1 2
3 4

Problem R2 · Substations

C++ (the episode's accepted code)

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<bool> cut;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    int kids = 0;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            kids++;
            low[v] = min(low[v], low[u]);
            if (pe != -1 && low[u] >= tin[v]) cut[v] = true;   // not for the root
        }
    }
    if (pe == -1 && kids > 1) cut[v] = true;   // root: two or more DFS children
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});              // (neighbour, road id)
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    cut.assign(n + 1, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    vector<int> ans;
    for (int v = 1; v <= n; v++) if (cut[v]) ans.push_back(v);
    cout << ans.size() << "\n";
    for (int v : ans) cout << v << " ";
}
2
3 4
1
1

Java (iterative; a child reports to its parent when it is popped, which is where kids is counted)

import java.io.*;
import java.util.*;

public class Main {
    static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
    static int nextInt() throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
    public static void main(String[] args) throws IOException {
        int n = nextInt(), m = nextInt();
        int[] ea = new int[m], eb = new int[m], start = new int[n + 2];
        for (int i = 0; i < m; i++) {
            ea[i] = nextInt(); eb[i] = nextInt();
            start[ea[i]]++; start[eb[i]]++;
        }
        for (int v = 1; v <= n + 1; v++) start[v] += start[v - 1];
        int[] to = new int[2 * m], rid = new int[2 * m];
        for (int i = 0; i < m; i++) {
            int p = --start[ea[i]]; to[p] = eb[i]; rid[p] = i;
            p = --start[eb[i]]; to[p] = ea[i]; rid[p] = i;
        }
        int[] tin = new int[n + 1], low = new int[n + 1], pe = new int[n + 1], par = new int[n + 1], it = new int[n + 1];
        int[] kids = new int[n + 1], stack = new int[n + 1];
        boolean[] cut = new boolean[n + 1];
        int timer = 0;
        for (int s = 1; s <= n; s++) {
            if (tin[s] != 0) continue;
            int top = 0;
            stack[top++] = s;
            tin[s] = low[s] = ++timer; pe[s] = -1; it[s] = start[s];
            while (top > 0) {
                int v = stack[top - 1];
                if (it[v] < start[v + 1]) {
                    int u = to[it[v]], id = rid[it[v]];
                    it[v]++;
                    if (id == pe[v]) continue;
                    if (tin[u] != 0) low[v] = Math.min(low[v], tin[u]);
                    else {
                        tin[u] = low[u] = ++timer; pe[u] = id; par[u] = v; it[u] = start[u];
                        stack[top++] = u;
                    }
                } else {
                    top--;
                    if (pe[v] != -1) {
                        int p = par[v];
                        kids[p]++;
                        low[p] = Math.min(low[p], low[v]);
                        if (pe[p] != -1 && low[v] >= tin[p]) cut[p] = true;   // not for the root
                    } else if (kids[v] > 1) cut[v] = true;                  // root: two or more DFS children
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for (int v = 1; v <= n; v++) if (cut[v]) { cnt++; sb.append(v).append(' '); }
        System.out.println(cnt);
        System.out.println(sb.toString().trim());
    }
}
2
3 4
1
1

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    ea = [int(x) for x in data[2:2 + 2 * m:2]]
    eb = [int(x) for x in data[3:3 + 2 * m:2]]
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = ea[i], eb[i]
        adj[a] += (b, i)
        adj[b] += (a, i)
    tin = [0] * (n + 1)
    low = [0] * (n + 1)
    pe = [-1] * (n + 1)
    par = [0] * (n + 1)
    it = [0] * (n + 1)
    kids = [0] * (n + 1)
    cut = [False] * (n + 1)
    timer = 0
    for s in range(1, n + 1):
        if tin[s]:
            continue
        timer += 1
        tin[s] = low[s] = timer
        stack = [s]
        while stack:
            v = stack[-1]
            av = adj[v]
            if it[v] < len(av):
                u, rid = av[it[v]], av[it[v] + 1]
                it[v] += 2
                if rid == pe[v]:
                    continue
                if tin[u]:
                    if tin[u] < low[v]:
                        low[v] = tin[u]
                else:
                    timer += 1
                    tin[u] = low[u] = timer
                    pe[u] = rid
                    par[u] = v
                    stack.append(u)
            else:
                stack.pop()
                if pe[v] != -1:
                    p = par[v]
                    kids[p] += 1
                    if low[v] < low[p]:
                        low[p] = low[v]
                    if pe[p] != -1 and low[v] >= tin[p]:
                        cut[p] = True         # not for the root
                elif kids[v] > 1:
                    cut[v] = True             # root: two or more DFS children
    ans = [v for v in range(1, n + 1) if cut[v]]
    print(len(ans))
    print(" ".join(map(str, ans)))

main()
2
3 4
1
1

Problem R3 · Backup Routes

C++ (the episode's accepted code; both dfs and paint are recursive)

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

int n, m, timer = 0;
vector<vector<pair<int, int>>> g;
vector<int> tin, low, comp;
vector<bool> isBridge;

void dfs(int v, int pe) {
    tin[v] = low[v] = ++timer;
    for (auto [u, id] : g[v]) {
        if (id == pe) continue;
        if (tin[u]) low[v] = min(low[v], tin[u]);
        else {
            dfs(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) isBridge[id] = true;
        }
    }
}
void paint(int v, int c) {                  // flood fill, never across a bridge
    comp[v] = c;
    for (auto [u, id] : g[v])
        if (!isBridge[id] && !comp[u]) paint(u, c);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    comp.assign(n + 1, 0);
    isBridge.assign(m, false);
    for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v, -1);
    int c = 0;
    for (int v = 1; v <= n; v++) if (!comp[v]) paint(v, ++c);
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (comp[a] == comp[b] ? "YES" : "NO") << "\n";
    }
}
YES
NO
YES
NO
YES

Java (iterative DFS and an iterative paint; 0.3 s with n, m, q = 2 · 10^5 on a path)

import java.io.*;
import java.util.*;

public class Main {
    static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
    static int nextInt() throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
    public static void main(String[] args) throws IOException {
        int n = nextInt(), m = nextInt();
        int[] ea = new int[m], eb = new int[m], start = new int[n + 2];
        for (int i = 0; i < m; i++) {
            ea[i] = nextInt(); eb[i] = nextInt();
            start[ea[i]]++; start[eb[i]]++;
        }
        for (int v = 1; v <= n + 1; v++) start[v] += start[v - 1];
        int[] to = new int[2 * m], rid = new int[2 * m];
        for (int i = 0; i < m; i++) {
            int p = --start[ea[i]]; to[p] = eb[i]; rid[p] = i;
            p = --start[eb[i]]; to[p] = ea[i]; rid[p] = i;
        }
        int[] tin = new int[n + 1], low = new int[n + 1], pe = new int[n + 1], par = new int[n + 1], it = new int[n + 1];
        int[] stack = new int[n + 1];
        boolean[] isBridge = new boolean[m];
        int timer = 0;
        for (int s = 1; s <= n; s++) {
            if (tin[s] != 0) continue;
            int top = 0;
            stack[top++] = s;
            tin[s] = low[s] = ++timer; pe[s] = -1; it[s] = start[s];
            while (top > 0) {
                int v = stack[top - 1];
                if (it[v] < start[v + 1]) {
                    int u = to[it[v]], id = rid[it[v]];
                    it[v]++;
                    if (id == pe[v]) continue;
                    if (tin[u] != 0) low[v] = Math.min(low[v], tin[u]);
                    else {
                        tin[u] = low[u] = ++timer; pe[u] = id; par[u] = v; it[u] = start[u];
                        stack[top++] = u;
                    }
                } else {
                    top--;
                    if (pe[v] != -1) {
                        int p = par[v];
                        low[p] = Math.min(low[p], low[v]);
                        if (low[v] > tin[p]) isBridge[pe[v]] = true;
                    }
                }
            }
        }
        int[] comp = new int[n + 1];
        int c = 0;
        for (int s = 1; s <= n; s++) {                         // paint with an explicit stack
            if (comp[s] != 0) continue;
            comp[s] = ++c;
            int top = 0;
            stack[top++] = s;
            while (top > 0) {
                int v = stack[--top];
                for (int j = start[v]; j < start[v + 1]; j++)
                    if (!isBridge[rid[j]] && comp[to[j]] == 0) { comp[to[j]] = c; stack[top++] = to[j]; }
            }
        }
        int q = nextInt();
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int a = nextInt(), b = nextInt();
            sb.append(comp[a] == comp[b] ? "YES" : "NO").append('\n');
        }
        System.out.print(sb);
    }
}
YES
NO
YES
NO
YES

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    ea = [int(x) for x in data[2:2 + 2 * m:2]]
    eb = [int(x) for x in data[3:3 + 2 * m:2]]
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = ea[i], eb[i]
        adj[a] += (b, i)
        adj[b] += (a, i)
    tin = [0] * (n + 1)
    low = [0] * (n + 1)
    pe = [-1] * (n + 1)
    par = [0] * (n + 1)
    it = [0] * (n + 1)
    is_bridge = [False] * m
    timer = 0
    for s in range(1, n + 1):
        if tin[s]:
            continue
        timer += 1
        tin[s] = low[s] = timer
        stack = [s]
        while stack:
            v = stack[-1]
            av = adj[v]
            if it[v] < len(av):
                u, rid = av[it[v]], av[it[v] + 1]
                it[v] += 2
                if rid == pe[v]:
                    continue
                if tin[u]:
                    if tin[u] < low[v]:
                        low[v] = tin[u]
                else:
                    timer += 1
                    tin[u] = low[u] = timer
                    pe[u] = rid
                    par[u] = v
                    stack.append(u)
            else:
                stack.pop()
                if pe[v] != -1:
                    p = par[v]
                    if low[v] < low[p]:
                        low[p] = low[v]
                    if low[v] > tin[p]:
                        is_bridge[pe[v]] = True
    comp = [0] * (n + 1)
    c = 0
    for s in range(1, n + 1):                 # paint with an explicit stack, never across a bridge
        if comp[s]:
            continue
        c += 1
        comp[s] = c
        stack = [s]
        while stack:
            v = stack.pop()
            av = adj[v]
            for j in range(0, len(av), 2):
                u = av[j]
                if not comp[u] and not is_bridge[av[j + 1]]:
                    comp[u] = c
                    stack.append(u)
    pos = 2 + 2 * m
    q = int(data[pos])
    out = []
    for i in range(q):
        a, b = int(data[pos + 1 + 2 * i]), int(data[pos + 2 + 2 * i])
        out.append("YES" if comp[a] == comp[b] else "NO")
    sys.stdout.write("\n".join(out) + "\n")

main()
YES
NO
YES
NO
YES