Articulation Point - II

JavaView on GFG

Time: O(V+E)

Space: O(V+E)

Problem Overview

Find all articulation points (cut vertices) in undirected graph.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find all articulation points (cut vertices) in undirected graph. DFS with disc/low arrays.

Algorithm

1DFS tracking discovery time disc[] and low[] (earliest reachable ancestor).
2Node u is AP if: (1) root with 2+ children, or (2) non-root with child v where low[v] >= disc[u].

Common Pitfalls

• Root special case: it is AP iff it has 2+ DFS children. Track parent to avoid parent edge as back edge.

Articulation Point - II.java

Java


// Approach: Run Tarjan's DFS tracking discovery time (tin) and lowest reachable time (low).
// A non-root node u is an articulation point if any child v has low[v] >= tin[u] (no back edge
// bypasses u). The root is an articulation point only if it has more than one DFS child.
// Time: O(V+E) Space: O(V+E)
import java.util.*;

class Solution {

    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[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] tin = new int[V];
        int[] low = new int[V];
        boolean[] vis = new boolean[V];
        boolean[] isArticulation = new boolean[V];
        int[] timer = {0};

        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                dfs(i, -1, adj, vis, tin, low, timer, isArticulation);
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (isArticulation[i]) {
                ans.add(i);
            }
        }

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

        return ans;
    }

    static void dfs(int u, int parent, ArrayList<ArrayList<Integer>> adj, boolean[] vis, int[] tin, int[] low,
            int[] timer, boolean[] isArticulation) {
        vis[u] = true;
        tin[u] = low[u] = timer[0]++;
        int children = 0;

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

            if (v == parent) {
                continue;
            }

            if (!vis[v]) {
                dfs(v, u, adj, vis, tin, low, timer, isArticulation);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] >= tin[u] && parent != -1) {
                    isArticulation[u] = true;
                }

                children++;
            } else {
                low[u] = Math.min(low[u], tin[v]);
            }
        }
        if (parent == -1 && children > 1) {
            isArticulation[u] = true;
        }
    }
}

Was this solution helpful?