Vertex and Edge Cut Algorithms¶
In graph theory, cut vertices (articulation points) and cut edges (bridges) play a crucial role in analyzing network connectivity. A cut vertex is a node whose removal increases the number of connected components, while a cut edge is a link whose removal does the same.
To find these points and edges, various algorithms exist – the most famous being Tarjan's algorithm. This algorithm uses DFS (Depth-First Search) and two key properties for each vertex: index (discovery time) and low_link (the lowest index reachable from that vertex through DFS edges).
typedef struct {
int index; // vertex number
int low_link; // vertex's lowest root
bool onStack; // is on the stack?
} TarjanNode;
Applications of these algorithms include identifying critical nodes in computer networks, analyzing social network vulnerabilities, and detecting communities in complex systems.
Finding Bridge Edges¶
To find bridge edges, we first run the DFS algorithm on the graph. While running the DFS algorithm, for each vertex u, we maintain a value dp[u] which equals the lowest height reachable via back edges from vertices in the subtree of u. The value dp[u] for each vertex is calculated as the minimum value among its children's values and the height of its own back edges.
An edge between vertex v and its parent parent[v] is a bridge if and only if the value of dp[v] is not less than the height of v. This means there is no edge in the subtree of v that connects to a vertex above v.
The runtime 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 Articulation Points¶
In this section, similar to finding bridges, we compute the dp[u] value using the same definition for vertex u. A vertex is an articulation point if removing it splits the graph into more than one component. Therefore, in the DFS tree we constructed, a vertex v is an articulation point if the dp value of all its children is greater than the height (depth) of vertex v, meaning no back edge exists to a higher ancestor. Note that the root is an articulation point if its degree is not one.
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 آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
