Articulation Points (or Cut Vertices) in a Graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more components. They are useful for designing reliable networks. For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.

Following are some example graphs with articulation points encircled with red color.

ArticulationPoints1

ArticulationPoints2

ArticulationPoints

class Solution {
    // Function to count number of articulation points
    // In undirected connected graph
    static int[] low, discovery;
    static int time, count;
    // Discovery[i] -> Discovery time of that node
    // Low[i]-> Discovery time of the lowest visited neighbor that 'i' can touch
    public static int findArticulationPoints(List<Integer>[] graph, int n) {
        boolean visited[] = new boolean[n];
        // Starting DFS from 0th vertex
        low = new int[n];
        discovery = new int[n];
        time = 0;
        count = 0;
        DFS(graph, 0, -1, visited);
        return count;
    }

    public static void DFS(List<Integer>[] graph, int node, int parent, boolean[] visited) {
        low[node] = time;
        discovery[node] = time;
        time++;
        visited[node] = true;
        int dfsCalls = 0;
        boolean isAP = false;
        for (int neighbor : graph[node]) {
            if (neighbor == parent)
                continue;
            if (visited[neighbor])
                low[node] = Math.min(low[node], discovery[neighbor]);
            else {
                DFS(graph, neighbor, node, visited);
                low[node] = Math.min(low[node], low[neighbor]);
                if (discovery[node] <= low[neighbor] && !isAP && node != 0) {
                    isAP = true;
                    count++;
                }
                dfsCalls++;
            }
        }
        // 0th node is our startng point, therefore with above formula it will always be AP
        // which might not be true, therefore we check the number of components connected to this node
        // Therefore if components>=2, then this node will also be an AP
        if (node == 0 && dfsCalls > 1) 
            count++;
    }
}