Q41 Count Strongly Connected Components (Kosaraju’s Algorithm)

import java.util.ArrayList;
import java.util.*;
import java.io.*;
import java.lang.*;

public class Solution {
	
	//Function to find number of strongly connected components in the graph.
	public static int stronglyConnectedComponents(int v, ArrayList<ArrayList<Integer>> edges) {
		
		// step-1 make a graph and a reverse graph
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        ArrayList<ArrayList<Integer>> graph2 = new ArrayList<>();
        
        for(int i = 0 ;i < v ; i++){
            graph.add(new ArrayList<>());
            graph2.add(new ArrayList<>());
        }
        
        for(ArrayList<Integer> edge : edges){
            int a = edge.get(0)  , b = edge.get(1);
            
            // System.out.println(a + " " + b);
            graph.get(a).add(b);
            graph2.get(b).add(a);
        }
        
		//make a stack and visited 
        LinkedList<Integer> st = new LinkedList<>();

        boolean visited[] = new boolean[v];
        
		//apply random DFS and store order while backtracking in stack
        for(int i = 0 ;i < v ; i++){
            if(visited[i] == false)
            dfs(graph , i , visited , st);
        }
        
		//reset visited 
        visited = new boolean[v];
        int ans =0;

		//now apply random DFS in order stored in the stack to find SCC
        while(st.size() > 0){
            int rem = st.removeFirst();
            
            if(visited[rem] == false){
                dfs2(graph2 , rem , visited);
                ans++;
            }
        }
        
        return ans;
	}

	public static void dfs(ArrayList<ArrayList<Integer>> graph , int source , boolean visited[] 
    , LinkedList<Integer> st){
        
        visited[source] = true;
        
        for(int nbr : graph.get(source)){
            if(visited[nbr] == false)
            dfs(graph , nbr , visited , st);
        }
        
        st.addFirst(source);
    }
    
    public static void dfs2(ArrayList<ArrayList<Integer>> graph , int source , boolean visited[]){
        
        visited[source] = true;
        
        for(int nbr : graph.get(source)){
            if(visited[nbr] == false)
            dfs2(graph , nbr , visited);
        }
    }

}