> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/articulation-points-or-cut-vertices-in-a-graph.md).

# 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.\
\
\ <br>

![ArticulationPoints1](https://media.geeksforgeeks.org/wp-content/cdn-uploads/ArticulationPoints1-129x300.png)

![ArticulationPoints2](https://media.geeksforgeeks.org/wp-content/cdn-uploads/ArticulationPoints21-300x177.png)

![ArticulationPoints](https://media.geeksforgeeks.org/wp-content/cdn-uploads/ArticulationPoints-300x189.png)

```java
import java.util.*;

class Solution {

    // Global time counter used during DFS
    private static int time;

    /**
     * Finds the number of articulation points in an undirected graph.
     *
     * @param graph Adjacency list representation of the graph
     * @param n     Number of vertices
     * @return      Count of articulation points
     */
    public static int findArticulationPoints(List<Integer>[] graph, int n) {

        boolean[] visited = new boolean[n];

        // discovery[u] = time when u is first visited in DFS
        int[] discovery = new int[n];

        // low[u] = earliest discovered vertex reachable from u
        //           (including back edges)
        int[] low = new int[n];

        // Marks whether a vertex is an articulation point
        boolean[] isArticulation = new boolean[n];

        time = 0;

        // Graph may not always be connected
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, -1, graph, visited, discovery, low, isArticulation);
            }
        }

        // Count articulation points
        int count = 0;
        for (boolean ap : isArticulation) {
            if (ap) count++;
        }

        return count;
    }

    /**
     * DFS traversal using Tarjan's algorithm
     */
    private static void dfs(
            int u,
            int parent,
            List<Integer>[] graph,
            boolean[] visited,
            int[] discovery,
            int[] low,
            boolean[] isArticulation) {

        visited[u] = true;
        discovery[u] = low[u] = time++;
        int children = 0; // Number of DFS children

        for (int v : graph[u]) {

            // Ignore the edge to parent
            if (v == parent) continue;

            // Case 1: Back edge
            if (visited[v]) {
                low[u] = Math.min(low[u], discovery[v]);
            }
            // Case 2: Tree edge
            else {
                children++;
                dfs(v, u, graph, visited, discovery, low, isArticulation);

                // After visiting child v, update low[u]
                low[u] = Math.min(low[u], low[v]);

                /**
                 * Non-root articulation point condition:
                 * If child v cannot reach an ancestor of u,
                 * then u is an articulation point.
                 */
                if (parent != -1 && low[v] >= discovery[u]) {
                    isArticulation[u] = true;
                }
            }
        }

        /**
         * Root articulation point condition:
         * Root is an AP if it has more than one DFS child.
         */
        if (parent == -1 && children > 1) {
            isArticulation[u] = true;
        }
    }
}
```