🚀Day 9. Articulation Point - II 🧠
💡 Problem Description:
The problem can be found at the following link: Question Link
Given an undirected graph with V vertices and E edges, the graph is provided as a 2D array edges[][] where each element edges[i] = [u, v] indicates an undirected edge between vertices u and v. Your task is to return all the articulation points (or cut vertices) in the graph.
An articulation point is a vertex whose removal (along with all its connected edges) increases the number of connected components in the graph.
Note: The graph may be disconnected, i.e., it may consist of more than one connected component. If no such point exists, return
{-1}.
Note: Sorry for the delayed upload; my Final Semester exams are underway. Best of luck with your coding journey!
🔍 Example Walkthrough:
Input:
V = 5
edges = [[0, 1], [1, 4], [4, 3], [4, 2], [2, 3]]Output:
[1, 4]Explanation:
Removing vertex 1 or 4 disconnects the graph. For instance, if vertex 1 is removed, the part of the graph connected to 1 becomes isolated from the rest of the components.
Example 2:
Input:
V = 4
edges = [[0, 1], [0, 2]]Output:
[0]Explanation:
Removing vertex 0 will increase the number of disconnected components from 1 to 3.
Constraints
1 ≤ V, E ≤ 10⁴
🎯 My Approach:
Optimized DFS Using Tarjan’s Algorithm
Algorithm Steps:
Convert the edge list to an adjacency list: Build an adjacency list from the given edges to represent the graph.
Use Tarjan’s DFS-based algorithm: During the DFS traversal, maintain two arrays:
disc[u]: The discovery time of vertex u.low[u]: The lowest discovery time reachable from u (including back-edges).
Identify Articulation Points:
For a non-root vertex u, if there is a child v such that
low[v] >= disc[u], then u is an articulation point.For the root vertex of the DFS, if it has more than one child, then it is an articulation point.
Handle Disconnected Graphs: Since the graph can be disconnected, run the DFS for every unvisited vertex.
🕒 Time and Auxiliary Space Complexity
Expected Time Complexity: O(V + E), as every vertex and edge is visited only once in the DFS traversal.
Expected Auxiliary Space Complexity: O(V + E), primarily for the recursion stack, the adjacency list, and the additional arrays used for tracking discovery times and low values.
📝 Solution Code
Code (C++)
class Solution {
public:
vector<int> articulationPoints(int V, vector<vector<int>>& edges) {
vector<vector<int>> adj(V);
for (auto& e : edges) adj[e[0]].push_back(e[1]), adj[e[1]].push_back(e[0]);
vector<int> disc(V, -1), low(V), res;
vector<bool> ap(V), vis(V);
int time = 0;
function<void(int, int)> dfs = [&](int u, int p) {
vis[u] = true;
disc[u] = low[u] = time++;
int children = 0;
for (int v : adj[u]) {
if (v == p) continue;
if (!vis[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (p != -1 && low[v] >= disc[u]) ap[u] = true;
++children;
} else {
low[u] = min(low[u], disc[v]);
}
}
if (p == -1 && children > 1) ap[u] = true;
};
for (int i = 0; i < V; ++i)
if (!vis[i]) dfs(i, -1);
for (int i = 0; i < V; ++i)
if (ap[i]) res.push_back(i);
return res.empty() ? vector<int>{-1} : res;
}
};Code (Java)
class Solution {
static ArrayList<Integer> articulationPoints(int V, int[][] edges) {
ArrayList<Integer>[] adj = new ArrayList[V];
for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(e[1]);
adj[e[1]].add(e[0]);
}
int[] disc = new int[V], low = new int[V];
boolean[] vis = new boolean[V], ap = new boolean[V];
int[] time = {0};
for (int i = 0; i < V; i++)
if (!vis[i]) dfs(i, -1, adj, disc, low, vis, ap, time);
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < V; i++)
if (ap[i]) res.add(i);
if (res.isEmpty()) res.add(-1);
return res;
}
static void dfs(int u, int p, ArrayList<Integer>[] adj, int[] disc, int[] low, boolean[] vis, boolean[] ap, int[] time) {
vis[u] = true;
disc[u] = low[u] = ++time[0];
int children = 0;
for (int v : adj[u]) {
if (!vis[v]) {
children++;
dfs(v, u, adj, disc, low, vis, ap, time);
low[u] = Math.min(low[u], low[v]);
if (p != -1 && low[v] >= disc[u]) ap[u] = true;
} else if (v != p)
low[u] = Math.min(low[u], disc[v]);
}
if (p == -1 && children > 1) ap[u] = true;
}
}Code (Python)
class Solution:
def articulationPoints(self, V, edges):
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
disc = [-1] * V
low = [-1] * V
vis = [False] * V
ap = [False] * V
time = [0]
def dfs(u, p):
vis[u] = True
disc[u] = low[u] = time[0] = time[0] + 1
children = 0
for v in adj[u]:
if not vis[v]:
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if p != -1 and low[v] >= disc[u]:
ap[u] = True
elif v != p:
low[u] = min(low[u], disc[v])
if p == -1 and children > 1:
ap[u] = True
for i in range(V):
if not vis[i]:
dfs(i, -1)
res = [i for i, val in enumerate(ap) if val]
return res if res else [-1]🎯 Contribution and Support:
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated