Articulation Points in a Graph Using Tarjan's Algorithm

102.6k
0

Given an undirected graph with V vertices numbered from 0 to V - 1 and an edge list, return all articulation points in ascending order.

Deleting an articulation point and all incident edges increases the number of connected components. The graph can initially contain multiple components, parallel edges, or self-loops. Return [-1] after finding no articulation point.

Example 1

Input: V = 7, edges = [[0,1],[1,2],[2,0],[0,3],[3,4],[4,5],[5,3],[5,6]]

Output: [0,3,5]

Explanation: Deleting vertex 0, 3, or 5 increases the number of connected components.

Example 2

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0]]

Output: [-1]

Explanation: Deleting any single vertex leaves a connected path among the remaining vertices.

Brute Force Approach

Count connected components in the original graph, then ignore one candidate vertex during a fresh traversal. A larger component count after deletion identifies an articulation point.

Comparing against the original component count supports graphs already containing multiple components. The scan naturally returns vertices in ascending order. Prerequisite concepts include DFS, connected components, adjacency lists, and vertex deletion simulation.

Algorithm

  • Build an undirected adjacency list so every vertex can access its connected neighbors.

  • Count the connected components of the original graph to establish the baseline connectivity.

  • Consider each vertex as a possible deletion candidate because removing an articulation point can increase the number of components.

  • Run DFS across all remaining unvisited vertices while ignoring the candidate vertex.

  • Count the resulting connected components after the candidate is excluded.

  • Record the candidate when its removal produces more components than the original graph.

  • Process vertices in ascending order so the recorded articulation points naturally follow ascending order.

  • Return all recorded vertices, or [-1] when no vertex increases the component count.

Dry Run

articulation-point-bruteforce-graph-matched

articulation-point-bruteforce-graph-matched

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to count components while ignoring one vertex.
int countComponents(int vertices,
const vector<vector<int>>& adjacency,
int removedVertex) {
vector<bool> visited(vertices, false);
int components = 0;
// Start traversal from every remaining unvisited vertex.
for (int start = 0; start < vertices; start++) {
if (start == removedVertex || visited[start]) continue;
components++;
stack<int> pending;
pending.push(start);
visited[start] = true;
while (!pending.empty()) {
int node = pending.top();
pending.pop();
for (int neighbor : adjacency[node]) {
if (neighbor != removedVertex && !visited[neighbor]) {
visited[neighbor] = true;
pending.push(neighbor);
}
}
}
}
return components;
}
public:
// Function to find articulation points by removing every vertex.
vector<int> articulationPoints(int vertices,
vector<vector<int>>& edges) {
vector<vector<int>> adjacency(vertices);
// Build the undirected adjacency list once.
for (const auto& edge : edges) {
adjacency[edge[0]].push_back(edge[1]);
adjacency[edge[1]].push_back(edge[0]);
}
int originalComponents = countComponents(vertices, adjacency, -1);
vector<int> answer;
// Compare component counts after removing every candidate vertex.
for (int removed = 0; removed < vertices; removed++) {
int remainingComponents = countComponents(
vertices, adjacency, removed
);
if (remainingComponents > originalComponents) {
answer.push_back(removed);
}
}
// Return -1 when no articulation point exists.
if (answer.empty()) return {-1};
return answer;
}
};
// Driver function with a hard-coded undirected graph.
int main() {
int vertices = 7;
vector<vector<int>> edges = {
{0, 1}, {1, 2}, {2, 0}, {0, 3},
{3, 4}, {4, 5}, {5, 3}, {5, 6}
};
Solution solution;
vector<int> answer = solution.articulationPoints(vertices, edges);
for (int node : answer) cout << node << " ";
return 0;
}

Complexity Analysis

Let V be the number of vertices and E be the number of edges.

Time Complexity: O(V×(V+E)), because every candidate vertex deletion triggers a traversal across all remaining vertices and edges.

Space Complexity: O(V+E), where the adjacency list, visited markers, traversal storage, and answer list store graph state.

Optimal Approach

A single DFS records discovery times and the earliest ancestor reachable from every subtree. A non-root current vertex node becomes an articulation point after finding a child satisfying low[child] >= discovery[node].

The DFS root follows a separate rule because no ancestor exists above the root. More than one DFS child means separate child subtrees depend on the root for connectivity. Edge IDs preserve correct behavior for parallel edges. Prerequisite concepts include DFS trees, back edges, discovery times, low-link values, and edge indexing.

Algorithm

  • Build an undirected adjacency list with neighbor and edge ID pairs so parallel edges can be handled correctly.

  • Initialize discovery, low, parent, and articulation-marker arrays because DFS needs both discovery order and ancestor reachability information.

  • Start DFS from every undiscovered vertex and assign an increasing discovery time to each visited vertex.

  • Skip only the exact parent edge ID and update low[node] using the discovery time of an already visited neighbor.

  • After a child DFS finishes, update low[node] using low[child] because the child's subtree may reach an ancestor of the current vertex.

  • Mark a non-root vertex when low[child] >= discovery[node] because that child subtree cannot reach an ancestor without passing through the current vertex.

  • Count DFS children separately for every root and mark the root when it has more than one DFS child because removing it separates those subtrees.

  • Collect all marked vertices in ascending order and return them, or return [-1] when no articulation point exists.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
struct Frame {
int node;
int parent;
int parentEdge;
int nextIndex;
int children;
};
public:
// Function to find articulation points using low-link values.
vector<int> articulationPoints(int vertices,
vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> adjacency(vertices);
// Store a unique id with every undirected edge occurrence.
for (int edgeId = 0; edgeId < static_cast<int>(edges.size()); edgeId++) {
int first = edges[edgeId][0];
int second = edges[edgeId][1];
adjacency[first].push_back({second, edgeId});
adjacency[second].push_back({first, edgeId});
}
vector<int> discovery(vertices, -1);
vector<int> low(vertices, -1);
vector<int> parent(vertices, -1);
vector<bool> isArticulation(vertices, false);
int timer = 0;
// Start a DFS tree from every undiscovered vertex.
for (int start = 0; start < vertices; start++) {
if (discovery[start] != -1) continue;
discovery[start] = low[start] = timer++;
stack<Frame> frames;
frames.push({start, -1, -1, 0, 0});
while (!frames.empty()) {
Frame& frame = frames.top();
int node = frame.node;
// Process the next adjacent edge from the current frame.
if (frame.nextIndex < static_cast<int>(adjacency[node].size())) {
auto [neighbor, edgeId] = adjacency[node][frame.nextIndex++];
if (edgeId == frame.parentEdge) continue;
if (discovery[neighbor] == -1) {
frame.children++;
parent[neighbor] = node;
discovery[neighbor] = low[neighbor] = timer++;
frames.push({neighbor, node, edgeId, 0, 0});
} else {
low[node] = min(low[node], discovery[neighbor]);
}
continue;
}
// Finish the vertex and apply root or non-root rules.
Frame finished = frame;
frames.pop();
if (finished.parent == -1) {
if (finished.children > 1) {
isArticulation[finished.node] = true;
}
continue;
}
low[finished.parent] = min(
low[finished.parent], low[finished.node]
);
if (parent[finished.parent] != -1 &&
low[finished.node] >= discovery[finished.parent]) {
isArticulation[finished.parent] = true;
}
}
}
vector<int> answer;
for (int node = 0; node < vertices; node++) {
if (isArticulation[node]) answer.push_back(node);
}
// Return -1 when no articulation point exists.
if (answer.empty()) return {-1};
return answer;
}
};
// Driver function with a hard-coded undirected graph.
int main() {
int vertices = 7;
vector<vector<int>> edges = {
{0, 1}, {1, 2}, {2, 0}, {0, 3},
{3, 4}, {4, 5}, {5, 3}, {5, 6}
};
Solution solution;
vector<int> answer = solution.articulationPoints(vertices, edges);
for (int node : answer) cout << node << " ";
return 0;
}

Complexity Analysis

Let V be the number of vertices and E be the number of edges.

Time Complexity: O(V+E), because DFS processes every vertex and undirected edge a constant number of times.

Space Complexity: O(V+E), where adjacency, discovery values, low-link values, DFS frames, markers, and answer storage represent graph state.

Interview follow-up Questions

No. Deleting a leaf removes no connection between other remaining vertices.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Input: N = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 Output: 3 Explanation: Cities 0 and 3 each reach two other cities within the threshold. The greater tied index is 3 ....

105.7k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge app...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0