Articulation Point (Cut Vertex)

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:

• disc[u] → discovery time of node

• low[u] → lowest reachable discovery time

• parent[u] → DFS parent

• visited[u] → visited or not

Core Idea (Tarjan’s Algorithm)

During DFS:

• Assign discovery time

• Track lowest reachable ancestor

• Detect articulation condition

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

• Time Complexity: O(V + E)

• Space Complexity: O(V)

Key Takeaways

• This is a Tarjan DFS low-link problem

• Uses:

  • discovery time

  • lowest reachable ancestor

• Two key conditions define articulation points

Pattern Recognition

If you see:

• “critical nodes”

• “disconnect graph”

• “cut vertices”

• “remove node affects connectivity”

Think:

Tarjan’s Algorithm (Articulation Points)