Find articulation points or cut vertices in a graph
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
Reading time: 15 minutes  Coding time: 12 minutes
A vertex in an undirected connected graph is an articulation point or cut vertex if and only if removing it, and the edges connected to it, splits the graph into multiple components.
Hint: Apply Depth First Search on a graph.
 Construct the DFS tree.
 A node which is visited earlier is a "parent" of those nodes which are reached by it and visited later.
 If any child of a node does not have a path to any of the ancestors of its parent, it means that removing this node would make this child disjoint from the graph. This means that this node is an articulation point.
 There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.
Now for a child, this path to the ancestors of the node would be through a backedge from it or from any of its children.
Complexity
 Worst case time complexity:
Ξ(V+E)
 Average case time complexity:
Ξ(V+E)
 Best case time complexity:
Ξ(V+E)
 Space complexity:
Ξ(V)
Pseudocode
h[root] = 0
par[v] = 1
dfs (v):
d[v] = h[v]
color[v] = gray
for u in adj[v]:
if color[u] == white
then par[u] = v and dfs(u) and d[v] = min(d[v], d[u])
if d[u] >= h[v] and (v != root or number_of_children(v) > 1)
then the edge v is a cut vertex
else if u != par[v])
then d[v] = min(d[v], h[u])
color[v] = black
where h[v]β=β height of vertex v in the DFS tree and d[v]β=βmin(h[w] where there is at least vertex u in subtree of v in the DFS tree where there is an edge between u and w).
Implementation
 C++
C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;
// Part of Cosmos by OpenGenus Foundation
const int MAXN = 1e4+5;
vector<int> adj[MAXN];
bool vis[MAXN], AP[MAXN];
int n, m, currTime, disc[MAXN];
int low[MAXN]; // low[i] is the minimum of visited currTime of all vertices which are reachable from i.
void init(){
currTime = 0;
for(int i = 1;i <= n; i++){adj[i].clear();vis[i]=false;AP[i]=false;disc[i]=0;low[i]=INT_MAX;}
}
void dfs(int u, int parent){
vis[u] = true;
disc[u] = low[u] = currTime+1;
int child = 0;
for(auto v : adj[u]){
if(v == parent) continue;
if(!vis[v]){
child = child+1;
currTime++;
dfs(v, u);
//check if subtree rooted at v has a connection to one of the ancestors of u.
low[u] = min(low[u], low[v]);
if(parent == 1 && child > 1)
AP[u] = true;
if(parent != 1 && low[v] >= disc[u])
AP[u] = true;
}else{
// back edge.
low[u] = min(low[u], disc[v]);
}
}
}
int main(){
cin >> n >> m; // n = number of vertices, m = number of edges
init();
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 1); //start from any random vertex, make its parent 1.
return 0;
}
Applications

Cut vertices denote the vertices that are critical in keeping the graph connected. Removing the vertex results in splitting of the graph.

Think of a cut vertex as a person who keeps five communities connected. The person may be a motivational activist. If this person is taken off consideration, then the five different communities become separate and hence, is detrimental as it results in discrimination. Thus, the person (cut vertex) is very important and must be supported.