Topics › Graphs › Other Algorithms

Articulation point in graph

Hard TUF ID 496 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an undirected graph with n vertices numbered 0 to n - 1 and a list of edges. A vertex is an articulation point (or cut vertex) if removing it, together with all its edges, increases the number of connected components. Return all articulation points in increasing order, or the list [-1] if there are none (this is the convention used by the GeeksforGeeks version of the problem).

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ edges ≤ 10^5, no self-loops. The original problem gives a connected graph; the code below also handles disconnected ones.

Example 1

n = 5, edges = [[0,1],[1,4],[2,3],[2,4],[3,4]]
answer = [1, 4]       // removing 1 isolates 0; removing 4 separates {0,1} from {2,3}

Example 2

n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
answer = [-1]         // a cycle: removing any one vertex leaves a path

Example 3

n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,1]]
answer = [1]          // a bow-tie: two triangles sharing vertex 1

Example 3 is the case that catches the most common implementation bug, explained in approach 2.

Approach 1: Brute force, remove each vertex and recount

Intuition. Use the definition directly. Count the connected components of the original graph. Then, for each vertex x, pretend it is gone and count the components of what remains. If the count went up, x was holding parts of the graph together.

Why compare with “greater than” the original count and not “different”? Removing a vertex that was isolated lowers the count by one (its own component disappears), and removing an ordinary vertex leaves it unchanged. Only a cut vertex makes it grow.

Algorithm.

1. Build the adjacency list and compute original = countComponents(no vertex removed).
2. For each x: compute countComponents(x removed) by marking x as already seen before the scan. If it is greater than original, add x.
3. Return the list, or [-1] if it is empty.

static List<List<Integer>> buildGraph(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    return adj;
}

static List<Integer> bruteForce(int n, int[][] edges) {
    List<List<Integer>> adj = buildGraph(n, edges);
    int original = countComponents(n, adj, -1);
    List<Integer> points = new ArrayList<>();
    for (int x = 0; x < n; x++) {
        if (countComponents(n, adj, x) > original) points.add(x);
    }
    if (points.isEmpty()) points.add(-1);
    return points;
}

static int countComponents(int n, List<List<Integer>> adj, int removed) {
    boolean[] seen = new boolean[n];
    if (removed >= 0) seen[removed] = true;                  // pretend the vertex is gone
    Deque<Integer> stack = new ArrayDeque<>();
    int count = 0;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        count++;
        seen[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    stack.push(v);
                }
            }
        }
    }
    return count;
}

Complexity. Time O(V · (V + E)): one full traversal per removed vertex. Space O(V + E). For 10^5 vertices that is far too slow, but it is a valuable reference implementation, and the Java file uses it to cross-check approach 2 on hundreds of random graphs.

Approach 2: Tarjan’s algorithm with discovery time and low-link

Intuition. Run one DFS and record for every vertex:

• tin[u]: the order in which DFS discovered u. Ancestors in the DFS tree always have smaller tin than their descendants.
• low[u]: the smallest tin that u’s subtree can reach using tree edges downward and then one back edge, without going back along the edge to u’s parent.

In an undirected DFS every non-tree edge joins a vertex to one of its ancestors. So when we delete a non-root vertex u, a child subtree v stays connected to the rest of the graph only if some vertex inside it has a back edge to a proper ancestor of u, that is, a vertex with tin strictly smaller than tin[u]. That gives the rule:

• Non-root u: u is an articulation point if it has some child v with low[v] ≥ tin[u]. Notice ≥, not > as for bridges: a back edge that lands exactly on u does not help, because u itself is being removed.
• Root of the DFS tree: it has no ancestors, so the rule above would always fire. Instead, the root is an articulation point exactly when it has more than one DFS child. Two DFS children of the root can only be linked through the root, otherwise DFS would have reached the second one from inside the first.

Why tin[v] and not low[v] on back edges. When u sees an already-visited neighbour v, we must use low[u] = min(low[u], tin[v]). The value low[v] describes what v can reach through its own other paths, and those paths may go through the very vertex we are testing. In example 3, DFS goes 0 → 1 → 2 (back edge 2-0 makes low[1] = 0), then 1 → 3 → 4, and 4 has a back edge to 1. With tin[1] = 1 we get low[3] = 1 ≥ tin[1], so 1 is a cut vertex, which is correct. With low[1] = 0 instead we would get low[3] = 0, and vertex 1 would be missed, because the path to 0 that low[1] describes runs through vertex 1 itself. The Java tests include this graph; swapping tin[v] for low[v] makes them fail.

Algorithm.

1. Build the adjacency list. Start a DFS from every unvisited vertex with parent = -1.
2. In dfs(u, parent): set tin[u] = low[u] = timer++ and children = 0.
3. For each neighbour v, skipping parent:
   • If v is unvisited: recurse, then low[u] = min(low[u], low[v]); if low[v] ≥ tin[u] and u is not the root, mark u; increment children.
   • Otherwise: low[u] = min(low[u], tin[v]).
4. After the loop, if u is the root and children > 1, mark u.
5. Collect marked vertices in increasing order (a vertex can be marked by several children, so use a boolean array, not a list), or return [-1].

static List<Integer> tarjan(int n, int[][] edges) {
    List<List<Integer>> adj = buildGraph(n, edges);
    int[] tin = new int[n], low = new int[n], timer = new int[1];
    boolean[] visited = new boolean[n], isCut = new boolean[n];
    for (int s = 0; s < n; s++) {
        if (!visited[s]) dfs(s, -1, adj, visited, tin, low, timer, isCut);   // every component
    }
    List<Integer> points = new ArrayList<>();
    for (int x = 0; x < n; x++) {
        if (isCut[x]) points.add(x);                         // a vertex can qualify via several children
    }
    if (points.isEmpty()) points.add(-1);
    return points;
}

static void dfs(int u, int parent, List<List<Integer>> adj, boolean[] visited,
                int[] tin, int[] low, int[] timer, boolean[] isCut) {
    visited[u] = true;
    tin[u] = low[u] = timer[0]++;
    int children = 0;
    for (int v : adj.get(u)) {
        if (v == parent) continue;
        if (!visited[v]) {
            dfs(v, u, adj, visited, tin, low, timer, isCut);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] >= tin[u] && parent != -1) isCut[u] = true;   // v's subtree cannot climb above u
            children++;
        } else {
            low[u] = Math.min(low[u], tin[v]);               // tin, not low: see the article
        }
    }
    if (parent == -1 && children > 1) isCut[u] = true;       // DFS root: needs two separate subtrees
}

Dry run on example 1. Adjacency: 0: [1], 1: [0, 4], 2: [3, 4], 3: [2, 4], 4: [1, 2, 3].

Answer [1, 4].

Complexity. Time O(V + E): a single DFS. Space O(V + E) for the graph, plus O(V) for the arrays and recursion stack.

Edge cases and pitfalls

• The root rule. Without the special case, the root always satisfies low[v] ≥ tin[root] = 0 and would always be reported. In a star (centre 0, leaves 1, 2, 3), the root is a cut vertex and is caught by children > 1.
• ≥ versus >. Articulation points use low[v] ≥ tin[u]; bridges use low[v] > tin[u]. Mixing them up is a classic bug.
• Duplicates in the answer. One vertex can satisfy the condition for several children. Marking a boolean array and collecting at the end avoids reporting it twice and also gives sorted output for free.
• Counting children. Only count DFS-tree children (neighbours that were unvisited when examined), not all neighbours.
• Tiny graphs. A single vertex or a single edge has no articulation points: return [-1].
• Disconnected input. Run DFS from every unvisited vertex, each as its own root.
• Recursion depth. A long path of 10^5 vertices can overflow Java’s default stack; use a thread with a larger stack or an explicit stack in production.

Related problems

• Bridges in graph uses the same tin and low arrays to find cut edges.
• Kosaraju’s algorithm decomposes directed graphs with a similar pair of DFS passes.
• Connected Components is the component counting used by the brute force.
• DFS covers the traversal the algorithm is built on.