Bridges and Articulation Points

Lesson 16 of 17 · Graphs and trees

A bridge is an edge whose removal splits the graph into two parts, and an articulation point is a vertex whose removal does that. These are the "weak points" of a network: one road, one router or one crossroads on which connectivity depends. All of them are found with one DFS traversal (Tarjan's algorithm).

Before you start: prerequisites – DFS.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

An example

  1 --- 2         5 --- 6
   \   /          |
    \ /           |
     3 --------- 4

The edges 1–2, 2–3, 1–3 form a cycle, so none of them is a bridge. The edges 3–4, 4–5 and 5–6 are bridges. The articulation points are 3, 4 and 5.

The idea: entry time and low

During DFS we give every vertex tin[v] – the order number of its entry. Then we calculate low[v]: the smallest tin that can be reached from the subtree of the vertex v, using edges of the DFS tree downwards and one "back" edge to an already visited vertex.

  • The edge v – u (u is a child in the DFS tree) is a bridge if low[u] > tin[v]: from the subtree of the vertex u there is no other way to v or above it.
  • The vertex v (which is not the root) is an articulation point if it has a child u with low[u] >= tin[v].
  • The root of the DFS tree is an articulation point if it has at least two children in the DFS tree.

The program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> graph;
vector<int> tin, low;
vector<bool> isArticulation;
vector<pair<int, int>> bridges;
int timer = 0;

void dfs(int v, int parent) {
    tin[v] = low[v] = ++timer;
    int children = 0;
    for (int u : graph[v]) {
        if (u == parent) continue;
        if (tin[u]) {                              // a back edge to a visited vertex
            low[v] = min(low[v], tin[u]);
        } else {                                   // an edge of the DFS tree
            dfs(u, v);
            children++;
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) bridges.push_back({min(u, v), max(u, v)});
            if (parent != 0 && low[u] >= tin[v]) isArticulation[v] = true;
        }
    }
    if (parent == 0 && children >= 2) isArticulation[v] = true;   // the root
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n + 1);
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    isArticulation.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int v = 1; v <= n; v++)
        if (!tin[v]) dfs(v, 0);                    // the graph may be disconnected
    sort(bridges.begin(), bridges.end());
    cout << "Bridges:";
    for (auto [a, b] : bridges) cout << " " << a << "-" << b;
    cout << endl << "Articulation points:";
    for (int v = 1; v <= n; v++) if (isArticulation[v]) cout << " " << v;
    cout << endl;
    return 0;
}

Example (the graph from the picture above)

Input

6 6
1 2
2 3
1 3
3 4
4 5
5 6

Output

Bridges: 3-4 4-5 5-6
Articulation points: 3 4 5

The complexity is O(n + m) – one traversal. This program assumes that there is at most one edge between two vertices; if there can be more, instead of the parent you should skip only the edge (by its index) along which we came.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

Critical roads

The network of roads between n villages is connected. A road is critical if closing it would leave some villages cut off. Print the number of critical roads.

Example 1

Input

6 6
1 2
2 3
1 3
3 4
4 5
5 6

Output

3

Example 2

Input

3 3
1 2
2 3
3 1

Output

0
Common mistakes and tips
  • In an undirected graph do not use the edge to the parent as a back edge.
  • For bridges the condition is low[u] > tin[v], and for articulation points low[u] >= tin[v].
  • The root of the DFS tree has a special condition: at least two children.

Check your knowledge

Open the quiz

Bridges and articulation points

1. What is a bridge in a graph?




2. Can an edge that lies on a cycle be a bridge?




3. When is the root of the DFS tree an articulation point?