Lab8q2.java

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

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

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

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

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();

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

        System.out.println("Enter each edge (format: start end):");
        for (int i = 0; i < edges; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            list.get(start).add(end);
        }

        System.out.println("\nAdjacency 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];
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                dfs(list, i, visited, stack);
            }
        }

        System.out.println("\nStack after DFS: " + stack);

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

        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        boolean[] visited2 = new boolean[vertices];
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited2[node]) {
                ans.add(realDFS(node, listRev, visited2));
            }
        }

        System.out.println("\nStrongly connected components are:");
        for (ArrayList<Integer> component : ans) {
            System.out.print("{ ");
            for (Integer element : component) {
                System.out.print(element + " ");
            }
            System.out.println("}");
        }

        scanner.close();
    }

    static ArrayList<Integer> realDFS(int node, ArrayList<ArrayList<Integer>> list, boolean[] visited2) {
        ArrayList<Integer> temp = new ArrayList<>();
        visited2[node] = true;
        temp.add(node);
        for (Integer element : list.get(node)) {
            if (!visited2[element]) {
                temp.addAll(realDFS(element, list, visited2));
            }
        }
        return temp;
    }

    static void dfs(ArrayList<ArrayList<Integer>> list, int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        for (int neighbor : list.get(v)) {
            if (!visited[neighbor]) {
                dfs(list, neighbor, visited, stack);
            }
        }
        stack.push(v);
    }
}