Articulation / Graph (NEW)

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjList;
    private int time;

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

    public void addEdge(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v);
    }

    public void findArticulationPoints() {
        boolean[] visited = new boolean[vertices];
        int[] dfn = new int[vertices];
        int[] low = new int[vertices];
        int[] parent = new int[vertices];
        Arrays.fill(parent, -1);

        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;
        dfn[u] = low[u] = ++time;
        int childCount = 0;
        boolean isArticulation = false;

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

                low[u] = Math.min(low[u], low[v]);

                if (parent[u] != -1 && low[v] >= dfn[u]) {
                    isArticulation = true;
                }

                if (parent[u] == -1 && childCount > 1) {
                    isArticulation = true;
                }
            } else if (v != parent[u]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (isArticulation) {
            System.out.println("Articulation Point: " + u);
        }
    }

    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++) {
                if (adjMatrix[i][j] == 1) {
                    g.addEdge(i, j);
                }
            }
        }
        return g;
    }

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

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

        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();
            }
        }

        Graph g = Graph.createGraphFromAdjMatrix(adjMatrix);

        System.out.println("Articulation Points:");
        g.findArticulationPoints();
    }
}





AlgorithmArt(u, v)
// u: Start vertex for Depth First Search (DFS)
// v: Parent of u in the DFS tree (if any)
// dfn: Global array initialized to 0, storing discovery times of vertices
// L: Global array to store the lowest discovery time reachable from each vertex
// num: Global variable initialized to 1, represents the discovery order
// n: Number of vertices in the graph

{
    dfn[u] := num;           // Assign discovery time for u
    L[u] := num;             // Initialize lowest discovery time for u
    num := num + 1;          // Increment discovery counter

    for each vertex w adjacent to u do
    {
        if (dfn[w] = 0) then  // If w is unvisited
        {
            Art(w, u);        // Recursively visit w
            L[u] := min(L[u], L[w]);  // Update the lowest discovery time for u
        }
        elseif (w ≠ v) then   // If w is not the parent of u
        {
            L[u] := min(L[u], dfn[w]); // Update the lowest discovery time
        }
    }
}
 AlgorithmBiComp(u, v)
// u: Start vertex for Depth First Search (DFS)
// v: Parent of u in the DFS tree (if any)
// dfn: Global array initialized to 0, storing discovery times of vertices
// L: Global array to store the lowest discovery time reachable from each vertex
// num: Global variable initialized to 1, represents the discovery order
// s: Stack to store edges
// n: Number of vertices in the graph

{
    dfn[u] := num;           // Assign discovery time for u
    L[u] := num;             // Initialize lowest discovery time for u
    num := num + 1;          // Increment discovery counter

    for each vertex w adjacent to u do
    {
        // Push edge (u, w) onto the stack if it exists and w is not the parent
        if ((w ≠ v) and (dfn[w] < dfn[u])) then
            Add edge (u, w) to the top of the stack s;

        if (dfn[w] = 0) then  // If w is unvisited
        {
            BiComp(w, u);     // Recursively apply BiComp on w

            if (L[w] > dfn[u]) then  // Found a new biconnected component
            {
                write("New biconnected component:");
                repeat
                {
                    Delete an edge from the top of stack s;
                    Let this edge be (x, y);
                    write(x, y);   // Output the edges in the component
                } until (((x, y) = (u, w)) or ((x, y) = (w, u))); 
            }

            L[u] := min(L[u], L[w]);  // Update the lowest discovery time for u
        }
        elseif (w ≠ v) then
        {
            L[u] := min(L[u], dfn[w]);  // Update the lowest discovery time if w is already visited
        }
    }
}