Articulation Points in a Graph

Hard
1682.

Articulation Points in a Graph

Articulation Points in a Graph is a hard coding problem on depth-first search and graph, asked in Amazon, Microsoft and Samsung interviews.

You are given an undirected graph with n vertices numbered 0 to n - 1; each edges[i] = [u, v] connects u and v. The graph need not be connected.

A vertex is an articulation point (a cut vertex) if deleting it, together with its edges, increases the number of connected components of the graph.

Return every articulation point in ascending order. If the graph has none, return [-1].

Example 1

Input
n = 5, edges = [[0,1],[1,4],[4,3],[4,2],[2,3]]
Output
[1,4]
Explanation
Removing 1 cuts 0 off; removing 4 separates {0, 1} from {2, 3}. The triangle 2–3–4 survives losing 2 or 3.

Example 2

Input
n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output
[-1]
Explanation
On a cycle every vertex has a way around, so no single deletion disconnects anything.

Example 3

Input
n = 3, edges = [[0,1],[1,2]]
Output
[1]

Constraints

  • 1 <= n <= 10^4
  • 0 <= edges.length <= 10^4
  • edges[i].length == 2
  • 0 <= u, v < n, u != v
  • there are no repeated edges
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var articulationPoints = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Articulation Points in a Graph — Problem & Solution

Articulation Points in a Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Articulation Points in a Graph is a hard coding problem on depth-first search and graph, asked in Amazon, Microsoft and Samsung interviews.

Problem statement

You are given an undirected graph with n vertices numbered 0 to n - 1; each edges[i] = [u, v] connects u and v. The graph need not be connected.

A vertex is an articulation point (a cut vertex) if deleting it, together with its edges, increases the number of connected components of the graph.

Return every articulation point in ascending order. If the graph has none, return [-1].

Example 1

Input: n = 5, edges = [[0,1],[1,4],[4,3],[4,2],[2,3]]
Output: [1,4]
Explanation: Removing 1 cuts 0 off; removing 4 separates {0, 1} from {2, 3}. The triangle 2–3–4 survives losing 2 or 3.

Example 2

Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: [-1]
Explanation: On a cycle every vertex has a way around, so no single deletion disconnects anything.

Example 3

Input: n = 3, edges = [[0,1],[1,2]]
Output: [1]

Constraints

  • 1 <= n <= 10^4
  • 0 <= edges.length <= 10^4
  • edges[i].length == 2
  • 0 <= u, v < n, u != v
  • there are no repeated edges

Hints for Articulation Points in a Graph

  1. Hint 1

    Run a DFS and record each vertex's discovery time disc[u]. Edges that go back to an ancestor are the only way a subtree can bypass its parent.

  2. Hint 2

    Let low[u] be the earliest discovery time reachable from u's subtree using tree edges down and at most one back edge up.

  3. Hint 3

    A non-root u is a cut vertex if some child v has low[v] >= disc[u]. The DFS root is a cut vertex exactly when it has two or more DFS children.

How to solve Articulation Points in a Graph

Tarjan's low-link technique finds every cut vertex in one DFS. A child subtree that cannot climb above u without passing through u gets disconnected when u is removed.

Approach

  1. Build the adjacency list. Set disc[u] = -1 for all u.
  2. For each undiscovered vertex, start a DFS as a root with parent -1.
  3. In dfs(u, parent): set disc[u] = low[u] = timer++. For each neighbour v: if undiscovered, recurse, count a child, set low[u] = min(low[u], low[v]), and mark u if parent != -1 and low[v] >= disc[u]; else if v != parent, set low[u] = min(low[u], disc[v]).
  4. After the loop, mark a root u if it has more than one DFS child.
  5. Collect marked vertices in ascending order, or return [-1] if there are none.

Why it works

In an undirected DFS every non-tree edge joins a vertex to one of its ancestors. If child v has low[v] >= disc[u], no vertex in v's subtree has an edge to a proper ancestor of u, so every path from that subtree to the rest of the graph passes through u — deleting u disconnects it. Conversely if every child can reach above u, all children stay attached to u's parent. A root has no ancestor, so it separates its subtrees exactly when it has more than one.

Complexity

  • Time — O(n + E)
  • Space — O(n + E)

Pitfalls

  • The root needs its own rule: low[v] >= disc[root] holds for every child of the root.
  • Update low[u] from a back edge with disc[v], not low[v].
  • A vertex can be found as a cut vertex through several children — mark it once, not once per child.
  • Restart the DFS from every undiscovered vertex: the graph may be disconnected.

Reference solution

Python

import sys
from typing import List

def articulationPoints(n: int, edges: List[List[int]]) -> List[int]:
    sys.setrecursionlimit(max(1000, 4 * n + 100))
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    disc = [-1] * n
    low = [0] * n
    cut = [False] * n
    timer = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in adj[u]:
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= disc[u]:
                    cut[u] = True
            elif v != parent:
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            cut[u] = True

    for u in range(n):
        if disc[u] == -1:
            dfs(u, -1)
    res = [u for u in range(n) if cut[u]]
    return res if res else [-1]

Java

static int apTimer;

public static int[] articulationPoints(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]); }
    int[] disc = new int[n], low = new int[n];
    boolean[] cut = new boolean[n];
    Arrays.fill(disc, -1);
    apTimer = 0;
    for (int u = 0; u < n; u++) if (disc[u] == -1) apDfs(adj, u, -1, disc, low, cut);
    List<Integer> res = new ArrayList<>();
    for (int u = 0; u < n; u++) if (cut[u]) res.add(u);
    if (res.isEmpty()) return new int[]{-1};
    int[] out = new int[res.size()];
    for (int i = 0; i < out.length; i++) out[i] = res.get(i);
    return out;
}

static void apDfs(List<List<Integer>> adj, int u, int parent, int[] disc, int[] low, boolean[] cut) {
    disc[u] = low[u] = apTimer++;
    int children = 0;
    for (int v : adj.get(u)) {
        if (disc[v] == -1) {
            children++;
            apDfs(adj, v, u, disc, low, cut);
            low[u] = Math.min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u]) cut[u] = true;
        } else if (v != parent) {
            low[u] = Math.min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1) cut[u] = true;
}

C++

static void apDfs(vector<vector<int>>& adj, int u, int parent, vector<int>& disc, vector<int>& low, vector<bool>& cut, int& timer) {
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            children++;
            apDfs(adj, v, u, disc, low, cut, timer);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u]) cut[u] = true;
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1) cut[u] = true;
}

vector<int> articulationPoints(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> disc(n, -1), low(n, 0);
    vector<bool> cut(n, false);
    int timer = 0;
    for (int u = 0; u < n; u++) if (disc[u] == -1) apDfs(adj, u, -1, disc, low, cut, timer);
    vector<int> res;
    for (int u = 0; u < n; u++) if (cut[u]) res.push_back(u);
    if (res.empty()) res.push_back(-1);
    return res;
}

JavaScript

var articulationPoints = function(n, edges) {
    var adj = [], disc = [], low = [], cut = [];
    for (var i = 0; i < n; i++) { adj.push([]); disc.push(-1); low.push(0); cut.push(false); }
    for (var k = 0; k < edges.length; k++) { adj[edges[k][0]].push(edges[k][1]); adj[edges[k][1]].push(edges[k][0]); }
    var timer = 0;
    var dfs = function(u, parent) {
        disc[u] = low[u] = timer++;
        var children = 0;
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (disc[v] === -1) {
                children++;
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (parent !== -1 && low[v] >= disc[u]) cut[u] = true;
            } else if (v !== parent) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (parent === -1 && children > 1) cut[u] = true;
    };
    for (var u = 0; u < n; u++) if (disc[u] === -1) dfs(u, -1);
    var res = [];
    for (var x = 0; x < n; x++) if (cut[x]) res.push(x);
    return res.length ? res : [-1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Graph Data Structure