Skip to content

Biconnected Components

Introduction

Before reading the following content, please be sure to understand the Graph Theory Concepts section.

Related reading: Cut Vertices and Bridges

Definition

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

In a connected undirected graph, for two vertices \(u\) and \(v\), if removing any single edge (only one edge can be removed) cannot disconnect them, we say \(u\) and \(v\) are edge-biconnected.

In a connected undirected graph, for two vertices \(u\) and \(v\), if removing any single vertex (only one vertex can be removed, and it cannot be \(u\) or \(v\) themselves) cannot disconnect them, we say \(u\) and \(v\) are vertex-biconnected.

Edge-biconnectivity is transitive. That is, if \(x,y\) are edge-biconnected and \(y,z\) are edge-biconnected, then \(x,z\) are edge-biconnected.

Vertex-biconnectivity is not transitive. A counterexample is shown in the figure below: \(A,B\) are vertex-biconnected, \(B,C\) are vertex-biconnected, but \(A,C\) are not vertex-biconnected.

bcc-counterexample.png

For a maximal edge-biconnected subgraph in an undirected graph, we call this subgraph an edge-biconnected component.

For a maximal vertex-biconnected subgraph in an undirected graph, we call this subgraph a vertex-biconnected component.

DFS Spanning Tree

For a connected undirected graph, we can start DFS from any vertex to obtain a DFS spanning tree of the original graph (with the starting vertex as the root). The edges on this spanning tree are called tree edges, and the edges not on the spanning tree are called non-tree edges.

Due to the properties of DFS, we can guarantee that for any non-tree edge connecting two vertices in the spanning tree, one of them is an ancestor of the other.

The DFS code is as follows:

Implementation 
1
2
3
4
5
void DFS(int p) {
  visited[p] = true;
  for (int to : edge[p])
    if (!visited[to]) DFS(to);
}

1
2
3
4
5
def DFS(p):
    visited[p] = True
    for to in edge[p]:
        if visited[to] == False:
            DFS(to)

Edge-Biconnected Components

Example: Luogu P8436【Template】Edge-Biconnected Components

For a graph with \(n\) vertices and \(m\) undirected edges, output the number of its edge-biconnected components and each component.

Tarjan Algorithm 1

The process of finding biconnected components using Tarjan is similar to finding strongly connected components. You may first read the Tarjan algorithm for Strongly Connected Components.

We consider first finding all bridges, then using DFS to find the edge-biconnected components.

Finding bridges can be referred to in the bridge section of Cut Vertices and Bridges.

Time complexity: \(O(n+m)\).

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
59
60
61
62
63
64
65
66
67
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m, ans;
int tot = 1, hd[N];

struct edge {
  int to, nt;
} e[M << 1];

void add(int u, int v) { e[++tot].to = v, e[tot].nt = hd[u], hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

bool bz[M << 1];
int bcc_cnt, dfn[N], low[N], vis_bcc[N];
vector<vector<int>> bcc;

void tarjan(int x, int in) {
  dfn[x] = low[x] = ++bcc_cnt;
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (dfn[v] == 0) {
      tarjan(v, i);
      if (dfn[x] < low[v]) bz[i] = bz[i ^ 1] = true;
      low[x] = min(low[x], low[v]);
    } else if (i != (in ^ 1))
      low[x] = min(low[x], dfn[v]);
  }
}

void dfs(int x, int id) {
  vis_bcc[x] = id, bcc[id - 1].push_back(x);
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (vis_bcc[v] || bz[i]) continue;
    dfs(v, id);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u == v) continue;
    uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (dfn[i] == 0) tarjan(i, 0);
  for (int i = 1; i <= n; i++)
    if (vis_bcc[i] == 0) {
      bcc.push_back(vector<int>());
      dfs(i, ++ans);
    }
  cout << ans << '\n';
  for (int i = 0; i < ans; i++) {
    cout << bcc[i].size();
    for (int j = 0; j < bcc[i].size(); j++) cout << ' ' << bcc[i][j];
    cout << '\n';
  }
  return 0;
}

Tarjan Algorithm 2

We first summarize an important property: in an undirected graph, edges in the DFS spanning tree are either tree edges or non-tree edges.

We relate this to the method for finding strongly connected components. In an undirected graph, as long as a component has no bridges, all its vertices are in the same strongly connected component in the DFS spanning tree.

Conversely, a strongly connected component in the DFS spanning tree corresponds to an edge-biconnected component in the original undirected graph.

It can be observed that the process of finding edge-biconnected components is essentially the same as finding strongly connected components.

Time complexity: \(O(n+m)\).

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
59
60
61
62
63
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 2];

int hd[N << 1], tot = 1;

void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

int bcc_cnt, sum;
int dfn[N], low[N];
bool vis[N];
vector<vector<int>> ans;
stack<int> st;

void tarjan(int u, int in) {
  low[u] = dfn[u] = ++bcc_cnt;
  st.push(u), vis[u] = true;
  for (int i = hd[u]; i; i = e[i].nt) {
    int v = e[i].to;
    if (i == (in ^ 1)) continue;
    if (!dfn[v])
      tarjan(v, i), low[u] = min(low[u], low[v]);
    else if (vis[v])
      low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    vector<int> t;
    t.push_back(u);
    while (st.top() != u)
      t.push_back(st.top()), vis[st.top()] = false, st.pop();
    st.pop(), ans.push_back(t);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u != v) uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i, 0);
  cout << ans.size() << '\n';
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].size() << ' ';
    for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

Difference Algorithm

Similar to Tarjan Algorithm 1, we first find all bridges, then use a difference method to find edge-biconnected components.

First, perform DFS on the original graph.

bcc-1.png

As shown in the figure above, black and green edges are tree edges, and red edges are non-tree edges. Each non-tree edge uniquely corresponds to a simple path composed of tree edges in the tree. We say this non-tree edge covers all edges on that simple path.

In the graph, green tree edges are at least covered by one non-tree edge, while black tree edges are not covered by any non-tree edge.

Obviously, non-tree edges and green tree edges cannot be bridges, while black tree edges must be bridges.

First consider a brute-force approach: for each non-tree edge, mark every tree edge it covers as green one by one. Time complexity: \(O(nm)\).

Consider optimizing with a difference method. For each non-tree edge, mark a -1 at the endpoint with smaller depth in the tree and a +1 at the endpoint with larger depth in the tree. Then compute the sum of marks inside the subtree of each vertex in \(O(n)\).

For a vertex \(u\), the sum of marks inside its subtree equals the number of non-tree edges covering the tree edge between \(u\) and \(fa_u\). If this value equals \(0\), then the tree edge between \(u\) and \(fa_u\) is a bridge.

Then use DFS to find the edge-biconnected components.

Time complexity: \(O(n+m)\).

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 1];

int hd[N], tot;

void add(int u, int v) { e[++tot] = {v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }  // Adjacency list (undirected edge)

using ll = long long;
#define P(x, y) ((ll)min(x, y) * N + (ll)max(x, y))
constexpr int hmod = 1e5 + 7;

struct hash {
  vector<ll> v1[hmod];
  vector<short> v2[hmod];

  short &operator[](ll x) {
    int y = x % hmod;
    for (int i = 0; i < v1[y].size(); i++)
      if (v1[y][i] == x) return v2[y][i];
    v1[y].push_back(x), v2[y].push_back(0);
    return v2[y].back();
  }
} re, be;  // Implement hash table using vector due to tight time and memory constraints

// re: check for duplicate edges, be: record if an edge is a bridge

// #define P(x, y) {min(x, y), max(x, y)}
// using pii = pair<int, int>;
// map<pii, int> re, be; // Use map for hash table when constraints are not tight

int dep[N], bz[N], sum[N];  // Record depth, difference value, subtree difference sum
int vis[N], fa[N];          // Record visited status, group number

void dfs(int x, int pre) {  // Calculate depth of each point and single-point difference
  if (dep[x] < dep[pre]) bz[x]++, bz[pre]--;  // Return to ancestor, update difference value
  if (dep[x]) return;
  dep[x] = dep[pre] + 1;
  for (int i = hd[x]; i; i = e[i].nt) dfs(e[i].to, x);
}

int dfs2(int x, int pre) {  // Process subtree difference
  if (vis[x] == 1) return sum[x];
  vis[x] = 1, sum[x] = bz[x];
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (dep[v] > dep[x] && !vis[v]) sum[x] += dfs2(v, x);
  }
  if (sum[x] == 0 && re[P(x, pre)] == 1) be[P(x, pre)] = 1;  // Record bridge
  return sum[x];
}

int cnt;
vector<int> ans[N];

void dfs3(int x) {  // Calculate biconnected components
  if (fa[x]) return;
  ans[cnt].push_back(x), fa[x] = cnt;
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (be[P(x, v)] != 1) dfs3(v);  // Not a bridge, recursively process subtree
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) cin >> u >> v, uadd(u, v), re[P(u, v)]++;
  for (int i = 1; i <= n; i++)
    if (!dep[i]) dfs(i, 0);
  for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs2(i, 0);
  for (int i = 1; i <= n; i++)
    if (!fa[i]) cnt++, dfs3(i);
  cout << cnt << '\n';
  for (int i = 1; i <= cnt; i++) {
    cout << ans[i].size() << ' ';
    for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}
#2788.「CEOI2015 Day1」Pipes

Given an undirected graph with \(N\) vertices and \(M\) edges, not necessarily connected. Treat each connected component as a subgraph, and output the bridges in each subgraph. You only have 16 MB of memory.

Solution

The main challenge of this problem is that you cannot store all edges.

Consider optimizing edge storage: if a non-tree edge is completely covered by another non-tree edge, then this edge is useless.

Use a union-find set to maintain this.

Vertex-Biconnected Components

Example: Luogu P8435【Template】Vertex-Biconnected Components

For a graph with \(n\) vertices and \(m\) undirected edges, output the number of its vertex-biconnected components and each component.

Tarjan Algorithm

You need to learn about cut vertices first. Refer to the cut vertex section in Cut Vertices and Bridges.

First, two properties are given:

  1. Two vertex-biconnected components share at most one common vertex, which must be a cut vertex.
  2. For a vertex-biconnected component, the vertex with the smallest dfn value in the DFS spanning tree must be either a cut vertex or the root.

Based on the second property, we classify and discuss:

  1. When this vertex is a cut vertex, it must be the root of the vertex-biconnected component, because once its parent is included, it remains a cut vertex.
  2. When this vertex is the tree root:
    1. If it has two or more subtrees, it is a cut vertex.
    2. If it has only one subtree, it is the root of a vertex-biconnected component.
    3. If it has no subtrees, treat it as a vertex-biconnected component.
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
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 1];

int hd[N], tot = 1;

void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

int ans;
int dfn[N], low[N], bcc_cnt;
int sta[N], top, cnt;
bool cut[N];
vector<int> dcc[N];
int root;

void tarjan(int u) {
  dfn[u] = low[u] = ++bcc_cnt, sta[++top] = u;
  if (u == root && hd[u] == 0) {
    dcc[++cnt].push_back(u);
    return;
  }
  int f = 0;
  for (int i = hd[u]; i; i = e[i].nt) {
    int v = e[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        if (++f > 1 || u != root) cut[u] = true;
        cnt++;
        do dcc[cnt].push_back(sta[top--]);
        while (sta[top + 1] != v);
        dcc[cnt].push_back(u);
      }
    } else
      low[u] = min(low[u], dfn[v]);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u != v) uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) root = i, tarjan(i);
  cout << cnt << '\n';
  for (int i = 1; i <= cnt; i++) {
    cout << dcc[i].size() << ' ';
    for (int j = 0; j < dcc[i].size(); j++) cout << dcc[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

Difference Algorithm

bcc-2.png

As shown in the figure above, black edges are tree edges, red edges are non-tree edges. Each non-tree edge uniquely corresponds to a simple path composed of tree edges in the tree.

Consider a new graph where each vertex corresponds to a tree edge in the original graph (represented by blue points in the figure). For each non-tree edge in the original graph, connect all blue points corresponding to the tree edges on the simple path in the tree into a connected component (represented by blue edges in the figure).

Thus, a vertex is not a cut vertex if and only if all blue points corresponding to its incident edges in the new graph belong to the same connected component.

Two vertices are vertex-biconnected if and only if all blue points corresponding to the tree edges on the path between them in the original tree belong to the same connected component. That is, each connected component formed by blue points is a vertex-biconnected component.

The connectivity between blue points can be maintained using a difference method similar to the one used for finding edge-biconnected components. Time complexity: \(O(n+m)\).

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