Problem Summary

This is a classic Tarjan’s Algorithm (DFS low-link technique) problem.

You are given an undirected graph.

You must find all vertices such that:

Removing that vertex increases the number of connected components.

If none exist → return {-1}.

Key Insight

A node is an articulation point if:

Case 1 (Root case)

If it is a DFS root and has more than 1 child

Case 2 (Non-root case)

If it has a child v such that:

low[v] >= disc[u]

Meaning:
Child cannot reach an ancestor of u without going through u.

Important Concepts

We maintain:

Core Idea (Tarjan’s Algorithm)

During DFS:

Conditions

1. Root node condition

if (parent[u] == -1 && children > 1)
→ articulation point

2. Non-root condition

if (parent[u] != -1 && low[v] >= disc[u])
→ articulation point

Example intuition

Graph:

1 ---- 4 ---- 2
       |
       3

Node 4 connects multiple parts
Removing it breaks graph → articulation point

Java Solution

import java.util.*;

class Solution {

    static int time = 0;

    static void dfs(int u, int parent, ArrayList<ArrayList<Integer>> adj,
                    boolean[] visited, int[] disc, int[] low,
                    boolean[] ap) {

        visited[u] = true;
        disc[u] = low[u] = ++time;

        int children = 0;

        for (int v : adj.get(u)) {

            if (!visited[v]) {
                children++;

                dfs(v, u, adj, visited, disc, low, ap);

                low[u] = Math.min(low[u], low[v]);

                // Case 1: root
                if (parent == -1 && children > 1) {
                    ap[u] = true;
                }

                // Case 2: non-root
                if (parent != -1 && low[v] >= disc[u]) {
                    ap[u] = true;
                }

            } else if (v != parent) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

    static ArrayList<Integer> articulationPoints(int V, int[][] edges) {

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        boolean[] ap = new boolean[V];

        time = 0;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, -1, adj, visited, disc, low, ap);
            }
        }

        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            if (ap[i]) result.add(i);
        }

        if (result.size() == 0) {
            result.add(-1);
        }

        return result;
    }
}

Complexity

Key Takeaways

Pattern Recognition

If you see:

Think:

Tarjan’s Algorithm (Articulation Points)