Problem Statement

Given an undirected graph with V vertices and adjacency list adj. Find all the vertices removing which (and edges through it) would increase the number of connected components in the graph. The graph may be initially disconnected. Return the vertices in ascending order. If there are no such vertices then returns a list containing -1.

Note: Indexing is zero-based i.e nodes numbering from (0 to V-1). There might be loops present in the graph.

Examples

Example 1:

Input: V = 5
adj = {
    {1, 2},
    {0, 2},
    {0, 1, 3, 4},
    {2, 4},
    {2, 3}
}

Output: [2]

Explanation: Removing node 2 splits the graph into two components. It is the only articulation point.

Example 2:

Input: V = 4
adj = {
    {1},
    {0, 2},
    {1, 3},
    {2}
}
Output: [1, 2]

Explanation: Removing node 1 or 2 breaks the graph into more connected components.

Example 3:

Input: V = 3
adj = {
    {1, 1},  // self-loop
    {0, 0, 2},
    {1}
}

Output: [-1]

Explanation: Although there are self-loops, removing any node doesn't disconnect the graph.

Different Approaches

1️⃣ DFS

Intuition:

A vertex of a graph is called a Articulation point when the component is divided into 2 or more components if that particular vertex is removed. Removing a vertex means to also remove all the edges that share the vertex.

Understanding:

Before moving to the algorithm, it is important to know about the two arrays that play a crucial role in the algorithm:

• Discovery time / Time of insertion Array: During the DFS call, the time when a node is visited first (discovered first), is called its time of insertion or discovery time. This array will store the discovery times of the nodes.
  • Usage: It helps keep track of when each node was first visited. This value is unique and incremental, meaning it increases as the DFS progresses.
• Lowest time of insertion Array: In this case, the current node refers to all its adjacent nodes except the parent and the visited nodes and takes the minimum lowest time of insertion into account. This array stores the lowest time of insertion for all nodes.
  • Usage: It helps determine whether a node can reach an ancestor via a back edge, which is essential for identifying articulation points.

To find out the bridges in the bridge problem, checks were made inside the DFS, if there exists any alternative path from the adjacent node to the current node. But here the same cannot be done as in this case, we are trying to remove the current node along with all the edges linked to it.

For that reason, here a check will be made if there exists any path from the adjacent node to the previous node of the current node. In addition to that, it must be ensured that the current node that we are trying to remove must not be the starting node.

How the two arrays help in identifying the bridges in a graph?

Consider two nodes, node u and node v, where v is the neighbor of u. Let us assume that tin[u] represents the discovery time of node u and low[v] represents the lowest discovery time reachable from node v.

If low[v] >= tin[u]:
It means that the subtree rooted at it cannot reach any node that was discovered before node (except through node). Therefore, if node is removed, the subtree rooted at it would be disconnected from the rest of the graph.

Thus, when the DFS calls to the descendants are completed, this condition can be checked to identify the articulation points.

Edge Cases:

Consider the following graph:

In the following graph, the starting node 0 has two adjacent nodes, but it is not an articulation point. To avoid this edge case, the number of children must be incremented only if the adjacent node is not previously visited.

Note: A single node can be found as the articulation point multiple times. Thus, To avoid the storing of duplicate nodes, the nodes will be stored in a hash array instead of directly inserting them in a simple array.

Approach:

1. Prepare arrays to keep track of visited nodes, discovery times, low values (the lowest discovery time reachable), and articulation point markers. Initialize a timer to record the discovery times.
2. Perform a DFS traversal for each unvisited node. Mark the current node as visited and set its discovery and low values to the current timer value, then increment the timer.
3. Traverse all adjacent nodes of the current node. If an adjacent node is not visited, recursively perform DFS for that node. After returning from the DFS call, update the low value of the current node.
4. Check if the current node is an articulation point based on the conditions involving low and discovery values. If true, mark it as an articulation point.
5. If the current node is the root of the DFS tree and has more than one child, mark it as an articulation point. After the DFS traversal, compile a list of all marked articulation points.
6. Return the list of articulation points in ascending order. If no articulation points are found, return -1.

Code: