class Solution {
    /** Idea: normal DFS, only addition is to add node in stack after completing each path traversal*/
    public ArrayList<Integer> topoSort(int V, int[][] edges) {
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Integer>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            
            adj.get(u).add(v);
        }
        
        Stack<Integer> st = new Stack<>();
        boolean[] visited = new boolean[V];
        
        for(int i=0; i<V; i++)
        {
            if(visited[i] == false)
            {
                dfs(adj, visited, i, st);
            }
        }
        
        while(!st.isEmpty())
        {
            res.add(st.pop());
        }
        return res;
    }
    
    public void dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, int node, Stack<Integer> st)
    {
        visited[node] = true;
        
        // traverse all neighbours
        for(int v : adj.get(node))
        {
            if(visited[v] == false)
            {
                dfs(adj, visited, v, st);
            }
        }
        st.push(node);
    }
}