Skip to content

Cut Vertices and Bridges

Related reading: Biconnected Component

For more rigorous definitions of cut vertices and bridges, refer to Graph Theory Concepts.

Cut Vertex

For an undirected graph, if removing a vertex increases the number of connected components in the graph, then that vertex is a cut vertex (also known as an articulation point).

Procedure

If we try to delete each vertex and check the connectivity of the graph, the complexity would be very high. Therefore, we introduce a commonly used algorithm: Tarjan.

First, consider the following graph:

It is easy to see that vertex 2 is a cut vertex, and it is the only one in this graph.

First, we assign timestamps (the order of visitation) according to the DFS order.

This information is stored in an array called dfn.

We also need another array low, which stores the smallest timestamp reachable without passing through its parent.

For example, low[2] is 1, and low[5] and low[6] are 3.

Then we start DFS. The criterion for determining whether a vertex is a cut vertex is: For a vertex \(u\), if there exists at least one vertex \(v\) (a child of \(u\)) such that \(low_v \geq dfn_u\), meaning \(v\) cannot reach an ancestor, then \(u\) is a cut vertex.

This criterion does not apply to the starting point of the search, which requires special consideration: If the starting point is not a cut vertex, then other paths can also reach all nodes, meaning the starting point only "searches downward once," i.e., it has only one child in the search tree. If the starting point has two or more children in the search tree, then it must be a cut vertex (imagine starting the search from vertex 2 in the above graph; the search tree should have two children: 3 or 4, and 5 or 6). If it has only one child, removing it will have no effect. For example, in the graph below, a cycle is formed.

When visiting the children of vertex 1, suppose we first DFS to vertex 2, mark it as visited, then recursively go down to vertex 4, which then goes to vertex 3. During backtracking, we find that vertex 3 has already been visited, so it is not a cut vertex.

The pseudocode for updating low is as follows:

\[ \begin{array}{ll} 1 & \textbf{if } v \text{ is a son of } u \\ 2 & \qquad \text{low}_u = \min(\text{low}_u, \text{low}_v) \\ 3 & \textbf{else} \\ 4 & \qquad \text{low}_u = \min(\text{low}_u, \text{dfn}_v) \\ \end{array} \]

Example

Luogu P3388 【Template】Cut Vertex (Articulation Point)

Example Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
Luogu P3388 【Template】Cut Vertex (Articulation Point)
*/
#include <iostream>
#include <vector>
using namespace std;
int n, m;  // n: number of vertices, m: number of edges
int dfn[100001], low[100001], idx, res;
// dfn: records the timestamp for each vertex
// low: the smallest index reachable without going through the parent, idx: timestamp, res: answer count
bool vis[100001], flag[100001];  // flag: answer, vis: marks if visited
vector<int> edge[100001];        // used to store the graph

void Tarjan(int u, int fa) {  // u: current vertex index, fa: parent index
  vis[u] = true;              // mark as visited
  low[u] = dfn[u] = ++idx;    // assign timestamp
  int child = 0;              // number of children for each vertex
  for (const auto &v : edge[u]) {  // visit all neighbors of this vertex (C++11)
    if (!vis[v]) {
      child++;                       // one more child
      Tarjan(v, u);                  // continue
      low[u] = min(low[u], low[v]);  // update the smallest reachable node index
      if (fa != u && low[v] >= dfn[u] && !flag[u]) {  // main logic
        // If not the root, and the smallest node reachable without going through the parent meets the cut vertex condition, and not marked yet
        // Condition: after removing the parent, it cannot connect further, meaning it can at most reach the parent
        flag[u] = true;
        res++;  // record answer
      }
    } else if (v != fa) {
      // If this node is not the parent, update the smallest reachable node index
      low[u] = min(low[u], dfn[v]);
    }
  }
  // Main logic: if it's the root, it needs at least 2 children
  if (fa == u && child >= 2 && !flag[u]) {
    flag[u] = true;
    res++;  // record answer
  }
}

int main() {
  cin >> n >> m;                  // read input
  for (int i = 1; i <= m; i++) {  // note vertices start from 1
    int x, y;
    cin >> x >> y;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }  // use vector to store graph
  for (int i = 1; i <= n; i++)  // because the Tarjan graph may not be connected
    if (!vis[i]) {
      idx = 0;       // initialize timestamp to 0
      Tarjan(i, i);  // start from vertex i, parent is itself
    }
  cout << res << endl;
  for (int i = 1; i <= n; i++)
    if (flag[i]) cout << i << " ";  // output result
  return 0;
}

Bridge (Without Multiple Edges)

Similar to cut vertices, these are called bridges.

For an undirected graph, if removing an edge increases the number of connected components in the graph, then that edge is called a bridge or cut edge. More rigorously, given a connected graph \(G=\{V,E\}\), \(e\) is one of its edges (i.e., \(e \in E\)). If \(G-e\) is disconnected, then edge \(e\) is a cut edge (bridge) of graph \(G\).

For example, in the graph below,

Bridge Example Graph

the red edge is a bridge.

Procedure

It is similar to finding cut vertices, with only one change: the condition becomes \(low_v>dfn_u\), and there is no need to consider the root node.

Bridges are independent of whether a node is the root. When finding cut vertices, we considered that vertex \(v\) cannot reach an ancestor (including the parent) without passing through its parent \(u\), so vertex \(u\) is a cut vertex. If \(low_v=dfn_u\), it means \(v\) can still reach the parent. If vertex \(v\) cannot reach an ancestor and has no other path back to the parent, then the edge \(u-v\) is a bridge.

Implementation

The following code finds bridges in an undirected graph without multiple edges. When isbridge[x] is true, (father[x],x) is a bridge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int low[MAXN], dfn[MAXN], idx;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  father[u] = fa;
  low[u] = dfn[u] = ++idx;
  for (const auto &v : G[u]) {
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else if (v != fa) {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
low = [0] * MAXN
dfn = [0] * MAXN
idx = 0
isbridge = [False] * MAXN
G = [[0 for i in range(MAXN)] for j in range(MAXN)]
cnt_bridge = 0
father = [0] * MAXN


def tarjan(u, fa):
    father[u] = fa
    idx = idx + 1
    low[u] = dfn[u] = idx
    for i in range(0, len(G[u])):
        v = G[u][i]
        if dfn[v] == False:
            tarjan(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > dfn[u]:
                isbridge[v] = True
                cnt_bridge = cnt_bridge + 1
        elif v != fa:
            low[u] = min(low[u], dfn[v])

Bridge (With Multiple Edges)

However, the above method for graphs without multiple edges fails for undirected graphs with multiple edges.

Because there may be more than one edge between two nodes, none of these edges will be bridges.

Procedure

One approach is to change the parameter fa to the ID of the edge just traversed (each edge has a unique ID), i.e., change "do not update using the parent node" to "do not update using the incoming edge."

Another simpler approach is to set a flag to indicate whether an edge to the parent has already been traversed. After setting the flag, when visiting the parent again, update normally.

The following code finds bridges in an undirected graph that may have multiple edges.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int low[MAXN], dfn[MAXN], idx;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  bool flag = false;
  father[u] = fa;
  low[u] = dfn[u] = ++idx;
  for (const auto &v : G[u]) {
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else {
      if (v != fa || flag)
        low[u] = min(low[u], dfn[v]);
      else
        flag = true;
    }
  }
}

Practice Problems

The Tarjan algorithm has many other applications, such as finding strongly connected components, graph condensation, and solving 2-SAT problems.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用