public class Solution { public int motherVertex(int v, ArrayList<ArrayList<Integer>> edges) { // Q42 graph playlist , based on kosraju //make graph ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for(int i = 0 ;i < v ; i++) graph.add(new ArrayList<>()); for(ArrayList<Integer> edge : edges){ int a = edge.get(0)-1 , b = edge.get(1)-1; graph.get(a).add(b); } //fire DFS and add nodes while backtracking boolean visited[] = new boolean[v]; LinkedList<Integer> st = new LinkedList<>(); for(int i = 0 ;i < v ; i++){ if(visited[i] == false) dfs(graph , i , visited , st); } //now our potential answer is stored in the top of the stack visited = new boolean[v]; count = 0; int potential = st.pop(); //apply DFS and check in count if all nodes are getting visited dfs2(graph , potential , visited); //return count if all nodes got visited; return count == v ? 1 : 0; } static int count; 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; count ++; for(int nbr : graph.get(source)){ if(visited[nbr] == false) dfs2(graph , nbr , visited); } } }