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); } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter