ArticulationPoint

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of vertices:");
        int v = sc.nextInt();
        int adj[][] = new int[v + 1][v + 1];

        System.out.println("Enter the adjacency matrix:");
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                adj[i][j] = sc.nextInt();
            }
        }

        System.out.println("Articulation points and the vertices they disconnect:");
        for (int i = 1; i <= v; i++) {
            boolean[] visited = new boolean[v + 1];
            int components = 0;

            List<List<Integer>> disconnectedGroups = new ArrayList<>();
            for (int j = 1; j <= v; j++) {
                if (j != i && !visited[j]) {
                    List<Integer> group = new ArrayList<>();
                    dfs(j, visited, adj, v, i, group);
                    disconnectedGroups.add(group);
                    components++;
                }
            }

            if (components > 1) {
                System.out.println("Vertex " + i + " is an articulation point.");
                System.out.println("Disconnected groups:");
                for (List<Integer> group : disconnectedGroups) {
                    System.out.println(group);
                }
            }
        }

        sc.close();
    }

    private static void dfs(int curr, boolean[] visited, int[][] adj, int v, int ignore, List<Integer> group) {
        visited[curr] = true;
        group.add(curr);

        for (int k = 1; k <= v; k++) {
            if (adj[curr][k] == 1 && k != ignore && !visited[k]) {
                dfs(k, visited, adj, v, ignore, group);
            }
        }
    }
}