Articulation Point - II

JavaView on GFG

Time: O(V+E)

Space: O(V+E)

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?