> 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;
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/articulation-points-or-cut-vertices-in-a-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.