| 19 | } |
| 20 | //Function to find number of strongly connected components in the graph. |
| 21 | public int kosaraju(int V, ArrayList<ArrayList<Integer>> adj) |
| 22 | { |
| 23 | //code here |
| 24 | boolean[] vis = new boolean[V]; |
| 25 | Stack<Integer> st = new Stack<Integer>(); |
| 26 | for (int i = 0; i < V; i++) { //O(N+N) |
| 27 | if (!vis[i]) { |
| 28 | dfs(i, vis, adj, st); |
| 29 | } |
| 30 | } |
| 31 | |
| 32 | ArrayList<ArrayList<Integer>> adjList = new ArrayList<ArrayList<Integer>>(); |
| 33 | for (int i = 0; i < V; i++) { |
| 34 | adjList.add(new ArrayList<Integer>()); |
| 35 | } |
| 36 | // E |
| 37 | for (int i = 0; i < V; i++) { |
| 38 | vis[i] = false; |
| 39 | for (Integer it : adj.get(i)) { |
| 40 | adjList.get(it).add(i); |
| 41 | } |
| 42 | } |
| 43 | int count = 0; |
| 44 | // n+n |
| 45 | while (!st.isEmpty()) { |
| 46 | int node = st.peek(); |
| 47 | st.pop(); |
| 48 | if (!vis[node]) { |
| 49 | count++; |
| 50 | dfsCount(node, vis, adjList); |
| 51 | } |
| 52 | } |
| 53 | return count; |
| 54 | |
| 55 | } |
| 56 | } |