Articulation Points
Strongly Connected Components & Bridges DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding Articulation Points in an Undirected Graph, Graph, Undirected Graph, Adjacency List, Graph Traversal, Depth-First Search, Connected Components, Time Complexity, Space Complexity, Recursion, Arrays, graph algorithms, graph components, graph properties, dfs, Articulation Points in Graph, Bridges in Graph (Tarjan's Algorithm), Connected Components.
Problem Statement: Given an undirected connected graph with V vertices, represented by an adjacency list adj, find all the vertices whose removal disconnects the graph into two or more connected components. Note: Vertices are numbered from 0 to V 1. Loops might be present in the graph. Input Format: The input will consist of: An integer V representing the number of vertices. An adjacency list adj where adj[i] contains a list of vertices adjacent to vertex i. Output Format: Return a list of integers representing the articulation points in ascending order. If no articulation points are found, return a list containing { 1}. Constraints: V will be between 1 and 10^5. The graph is connected. Example 1: Input: V = 5 edges = [[0,1], [1,2], [2,0], [2,3], [3,4]] Graph Visual: Output: {2} Explanation: If we remove node 2, the graph will be divided into two components: {0, 1} and {3, 4}. Removing node 0 or 1 does not disconnect the graph. Example 2: Input: V = 5 edges = [[0,1], [1,4], [2,4], [2,3], [3,4]] Graph Visual: Output: {1, 4} Explanation: If we remove either node 1 or node 4, the graph breaks into multiple components.