Command Palette

Search for a command to run...

Hectal
Problem 37.2 · Advanced Graph AlgorithmsHard

Articulation Points

PatternGraph DFS and Flood Fill

What it teaches: The node version of low-link: a child that can't climb above its parent.

In plain words

A node is a weak spot if removing it splits the graph. DFS stamps visit times and low values like in the bridges problem. A non-root node u is a weak spot if some child can't climb back above u (low[child] ≥ disc[u]). The root is a weak spot only if it has two or more DFS children.

Return the weak-spot nodes in ascending order. Example: n = 5, [[0,1],[1,2],[2,0],[1,3],[3,4]] → [1, 3].

The problem

Given a connected undirected graph with n nodes, return every node whose removal disconnects the graph, in ascending order.

Example 1

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

Constraints

  • 1 ≤ n ≤ 10⁴
  • Connected

Pattern clues in the wording

  • → Single node of failure

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public List<Integer> articulationPoints(int n, int[][] edges) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
n = 5
edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
[1,3]
2
n = 3
edges = [[0,1],[1,2],[2,0]]
[]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Tarjan articulation points · O(V + E)
1

Tarjan articulation points

Time O(V + E) Space O(V + E)

DFS with disc/low; mark u when the rule holds; collect marked nodes in order.

▶ Dry run: Tarjan: low[child] ≥ disc[u]n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
01234

disc / low(map)

0: 0 / 01: 1 / 02: 2 / 0

Step 1/4DFS 0 → 1 → 2. 2 has a back edge to 0, so low[2] = 0. That is below disc[1] = 1, so this child doesn't make 1 a weak spot.

Approach 1
import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private int[] disc, low;
    private boolean[] cut;
    private int time = 0;

    public List<Integer> articulationPoints(int n, int[][] edges) {
        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]); }
        disc = new int[n];
        low = new int[n];
        cut = new boolean[n];
        Arrays.fill(disc, -1);
        dfs(0, -1);
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < n; i++) if (cut[i]) out.add(i);
        return out;
    }

    private void dfs(int u, int parent) {
        disc[u] = low[u] = time++;
        int children = 0;
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            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 {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (parent == -1 && children > 1) cut[u] = true;
    }
}

Verdict: Same DFS as bridges, different test.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single node
  • A cycle (none)
  • A path (all inner nodes)

Mistakes people make

  • Applying the low ≥ disc rule to the root.

Interview

Follow-up questions

What are biconnected components?