Lab8q1.java

import java.util.ArrayList;

public class Lab8q1 {
    public static void main(String[] args) {
        Lab8q1 p = new Lab8q1();
        
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int vertices = 4;

        for (int i = 0; i < vertices; i++) {
            list.add(new ArrayList<>());
        }

        
        list.get(0).add(1);
        list.get(0).add(2);
        list.get(1).add(3);
        list.get(2).add(1);
        list.get(3).add(2);

        System.out.println("Adjacency list is:");
        for (int j = 0; j < list.size(); j++) {
            System.out.print(j + " : { ");
            for (Integer element : list.get(j)) {
                System.out.print(element + " ");
            }
            System.out.println("}");
        }

        
        boolean[] visited = new boolean[vertices];
        p.dfs(list, 0, visited);

        
        for (boolean v : visited) {
            if (!v) {
                System.out.println("The graph is not strongly connected.");
                return;
            }
        }

        
        ArrayList<ArrayList<Integer>> listRev = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            listRev.add(new ArrayList<>());
        }

        for (int i = 0; i < vertices; i++) {
            for (int neighbor : list.get(i)) {
                listRev.get(neighbor).add(i);
            }
        }

        System.out.println("Reverse Adjacency list is:");
        for (int j = 0; j < listRev.size(); j++) {
            System.out.print(j + " : { ");
            for (Integer element : listRev.get(j)) {
                System.out.print(element + " ");
            }
            System.out.println("}");
        }

        
        visited = new boolean[vertices];
        p.dfs(listRev, 0, visited);

        
        for (boolean v : visited) {
            if (!v) {
                System.out.println("The graph is not strongly connected.");
                return;
            }
        }

        System.out.println("The graph is strongly connected.");
    }

    void dfs(ArrayList<ArrayList<Integer>> list, int v, boolean[] visited) {
        // Mark the current node as visited
        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex
        for (int neighbor : list.get(v)) {
            if (!visited[neighbor]) {
                dfs(list, neighbor, visited);
            }
        }
    }
}