articulation point

import java.util.*;

public class Graph {
    private int vertices;  // Number of vertices
    private LinkedList<Integer>[] adjList;  // Adjacency list representation
    private int time;  // Time counter for DFS

    // Constructor
    public Graph(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
        time = 0;
    }

    // Add an edge to the graph
    public void addEdge(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v);  // Since the graph is undirected
    }

    // Articulation Point (Art) Algorithm
    public void findArticulationPoints() {
        boolean[] visited = new boolean[vertices];
        int[] dfn = new int[vertices];  // Discovery time of visited vertices
        int[] low = new int[vertices];  // Lowest discovery time reachable
        int[] parent = new int[vertices];  // Parent vertices in DFS
        Arrays.fill(parent, -1);  // Initialize all parents as -1

        // Start DFS from each unvisited node
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                DFSArt(i, visited, dfn, low, parent);
            }
        }
    }

    private void DFSArt(int u, boolean[] visited, int[] dfn, int[] low, int[] parent) {
        visited[u] = true;  // Mark the current node as visited
        dfn[u] = low[u] = ++time;  // Initialize discovery time and low value
        int childCount = 0;  // Count of children in DFS tree
        boolean isArticulation = false;

        for (int v : adjList[u]) {
            if (!visited[v]) {
                childCount++;
                parent[v] = u;
                DFSArt(v, visited, dfn, low, parent);

                // Check if the subtree rooted at v has a connection back to one of u's ancestors
                low[u] = Math.min(low[u], low[v]);

                // u is an articulation point in two cases:
                // (1) u is not the root and low value of one of its child is more than discovery value of u
                if (parent[u] != -1 && low[v] >= dfn[u]) {
                    isArticulation = true;
                }

                // (2) u is the root of DFS tree and has two or more children
                if (parent[u] == -1 && childCount > 1) {
                    isArticulation = true;
                }
            } else if (v != parent[u]) {
                // Update low value of u for back edge
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        // If u is an articulation point, print it
        if (isArticulation) {
            System.out.println("Articulation Point: " + u);
        }
    }

    // Construct graph from adjacency matrix
    public static Graph createGraphFromAdjMatrix(int[][] adjMatrix) {
        int n = adjMatrix.length;
        Graph g = new Graph(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {  // Undirected graph, so only check i < j
                if (adjMatrix[i][j] == 1) {
                    g.addEdge(i, j);
                }
            }
        }
        return g;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input the number of vertices
        System.out.print("Enter the number of vertices: ");
        int v = scanner.nextInt();

        // Input the adjacency matrix
        System.out.println("Enter the adjacency matrix:");
        int[][] adjMatrix = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                adjMatrix[i][j] = scanner.nextInt();
            }
        }

        // Create the graph from adjacency matrix
        Graph g = Graph.createGraphFromAdjMatrix(adjMatrix);

        // Find and print the articulation points
        System.out.println("Articulation Points:");
        g.findArticulationPoints();
    }
}

output1:
Enter the number of vertices: 5
Enter the adjacency matrix:
0 1 1 0 0
1 0 1 1 0
1 1 0 0 0
0 1 0 0 1
0 0 0 1 0
Articulation Points:
Articulation Point: 1
Articulation Point: 3

output2:
Enter the number of vertices: 6
Enter the adjacency matrix:
0 1 1 0 0 0
1 0 1 1 0 0
1 1 0 0 1 0
0 1 0 0 1 1
0 0 1 1 0 1
0 0 0 1 1 0
Articulation Points:
Articulation Point: 2
Articulation Point: 3