December 27, 2025 — Vertex Biconnectivity, Cut Vertices, and Bridges
Introduction
Good Bye 2025, here I come!!!
You have no egg!
Connected Components (Maximally Connected Subgraphs)
A subgraph is formed by selecting some vertices and edges from the original graph to create a new graph.
A connected subgraph must satisfy the condition that the entire subgraph is connected.
A maximally connected subgraph aims to include as many vertices and edges as possible while remaining connected. Note that it is "maximal," not "maximum."
Maximal: Adding any more vertices or edges would break the condition!
Cut Vertices:
In an undirected graph, if removing a vertex increases the number of maximally connected components, that vertex is called a cut vertex (or articulation point).
First, consider the following graph:
We can see that the cut vertex is 2, and this graph has only this one cut vertex.
First, assign timestamps (DFS order) to the vertices.
If for a vertex ( u ), there exists a child ( v ) that cannot reach any vertex with a timestamp earlier than ( u ), then ( u ) is a cut vertex.
This is because after removing ( u ), the subtree containing ( v ) has no back edges to reconnect.
But what if it is the root node?
If the root node has two or more children in the DFS tree, it is a cut vertex.
Otherwise, if it has only one child, it is not a cut vertex.
Code:
inline void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idx;
bool flag = false;
int cnt = 0;
for (auto v : edges[u]) {
if (!dfn[v]) {
cnt++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != fa && !flag) {
flag = 1;
c.push_back(u);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (!flag && u == fa && cnt > 1) {
c.push_back(u);
}
}
Bridges:
Similar to cut vertices, bridges are also called cut edges.
In an undirected graph, if removing an edge increases the number of connected components, that edge is called a bridge or cut edge.
For example, in the following graph:
The red edges are bridges.
If there are no multiple edges between the same pair of vertices, simply change ( low_v \ge dfn_u ) to ( low_v > dfn_u ) in the cut vertex algorithm.
If there are multiple edges, they are definitely not bridges.
We can ignore the first edge.
Code:
inline void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idx;
int mark = 0, flag = 0;
for (auto [v, id] : edges[u]) {
if (v == fa && !mark) {
mark = 1;
} else if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
flag = 1;
ans.push_back(id);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
Biconnected Components (Vertex Biconnected Components):
A biconnected component (vertex biconnected component) is a connected component that remains connected after removing any single vertex.
As shown in the figure:
- Two biconnected components share at most one common vertex, which is a cut vertex.
- For a biconnected component, the vertex with the smallest ( dfn ) in the DFS tree must be a cut vertex or the root node.
Thus, we can use a stack to record visited vertices. During the backtracking phase after encountering a cut vertex, we can extract the biconnected components.
Note: Isolated vertices.
Code:
inline void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idx;
stk[++top] = u;
for (auto v : edges[u]) {
if (v == fa) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
vector<int> ve{u};
cnt[u]++;
while (ve.back() != v) {
ve.push_back(stk[top]);
cnt[stk[top]]++;
top--;
}
bcc.pb(ve);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (u == fa && cnt[u] == 0) {
bcc.pb({u});
}
}
Example Problem:
If ( u ) is a cut vertex and separates vertices ( A ) and ( B ) into two sides, then this vertex is valid.
If ( dfn_v \le dfn_B ), it is valid. We can then count the answers.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define sz(x) ((int)x.size())
#define inf (1 << 30)
#define pb push_back
typedef pair<int, int> PII;
const int N = 5e5 + 7;
const int P = 998244353;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (!(ch >= '0' && ch <= '9')) {
if (ch == '-') f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int n, m, a, b;
vector<int> edges[N], ans;
int dfn[N], low[N], idx;
inline void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idx;
bool flag = false;
int cnt = 0;
for (auto v : edges[u]) {
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
cnt++;
if (low[v] >= dfn[u] && !flag && u != fa && dfn[b] >= dfn[v]) {
flag = 1;
ans.push_back(u);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (!flag && u == fa && cnt > 1) {
ans.push_back(u);
}
}
int fa[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x != y) fa[x] = y;
}
void solve() {
n = read();
int x, y;
for (int i = 1; i <= n; i++) fa[i] = i;
while (scanf("%d%d", &x, &y)) {
if (x == 0 && y == 0) break;
m++;
unite(x, y);
edges[x].pb(y);
edges[y].pb(x);
}
if (find(x) != find(y)) {
puts("No solution");
return;
}
a = read(), b = read();
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i, i);
}
}
if (ans.size() == 0) {
puts("No solution");
return;
}
sort(ans.begin(), ans.end());
printf("%d\n", *ans.begin());
}
int main() {
int oT_To = 1;
while (oT_To--) solve();
return 0;
}
Comments (0)
