Cut Vertex and Bridge Algorithms¶
Finding Bridges¶
To find bridges, we first execute the DFS algorithm on the graph. While the DFS algorithm is running, for each vertex u, we maintain a dp[u] value, which is the lowest height reachable by a back-edge from any vertex in the subtree of vertex u. The dp[u] value for each vertex is calculated as the minimum of the dp values of its children and the heights of its own back-edges. Now, an edge between vertex v and parent[v] is a bridge if and only if dp[v] is not less than height[v]. This means that there is no back-edge from the subtree rooted at v that reaches a vertex with a height strictly less than height[v].
The time complexity of this algorithm is O(n+m), where n represents the number of vertices and m represents the number of edges.
const int maxn = 1e6 + 10;
bool mark[maxn], is[maxn];
int dp[maxn], height[maxn];
pair<int, int> edge[maxn];
vector<pair<int, int> > adj[maxn];
void dfs(int v,int parent,int index){
dp[v] = height[v];
mark[v] = true;
for(int i = 0; i < adj[v].size(); i++){
int u = adj[v][i].first;
int ind = adj[v][i].second;
if(!mark[u]){
height[u] = height[v] + 1;
dfs(u, v, ind);
dp[v] = min(dp[v], dp[u]);
}
else{
if(u != parent){
dp[v] = min(dp[v], height[u]);
}
}
}
if(v != 1 && dp[v] == height[v])
is[index] = true;
return;
}
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
edge[i] = {u, v};
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
dfs(1, 0, 0);
for(int i = 0; i < m; i++)
if(is[i])
cout << edge[i].first << " " << edge[i].second << endl;
return 0;
}
Finding Cut Vertices¶
In this section, similar to finding bridges, we compute dp[u] for vertex u using the same definition. A vertex v is a cut vertex if its removal divides the graph into more than one connected component. In the DFS tree we built, a non-root vertex v is a cut vertex if there exists a child u such that dp[u] is greater than or equal to height[v]. This implies that no back-edge from the subtree rooted at u reaches a vertex strictly higher than v. Note that the root of the DFS tree is a cut vertex if it has more than one child in the DFS tree.
The time complexity of this algorithm is also O(n+m).
const int maxn = 1e6 + 10;
bool mark[maxn], is[maxn];
int dp[maxn], height[maxn];
vector<int> adj[maxn];
void dfs(int v,int parent){
dp[v] = height[v];
mark[v] = true;
int num = 0;
for(int i = 0; i < adj[v].size(); i++){
int u = adj[v][i];
if(!mark[u]){
height[u] = height[v] + 1;
dfs(u, v);
if(v != 1 && dp[u] >= height[v])
is[v] = true;
dp[v] = min(dp[v], dp[u]);
num++;
}
else if(u != parent)
dp[v] =min(dp[v], height[u]);
}
if(v == 1 && num > 1)
is[v] = true;
return;
}
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
for(int u = 1; u <= n; u++)
if(is[u])
cout << u << " ";
return 0;
}
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
