toposort.java

import java.util.ArrayList;
import java.util.Stack;

public class toposort {
    static ArrayList<Integer> topologicalSort(ArrayList<ArrayList<Integer>> adj) {
        // Your code here
        int V=adj.size();
        int visited[]=new int[V];
        Stack<Integer> st=new Stack<Integer>();
        
        for(int i=0;i<V;i++){
            if(visited[i]==0){
                dfs(i,visited,st,adj);
            }
        }
        
        
        ArrayList<Integer> ans=new ArrayList<Integer>();
        while(!st.isEmpty()){
            int i=st.peek();
            ans.add(i);
            st.pop();
        }
        
        return ans;
        
    }
    
    static void dfs(int node,int visited[], Stack<Integer> st,ArrayList<ArrayList<Integer>> ad){
        visited[node]=1;
        
        for(int i:ad.get(node)){
            if(visited[i]!=1){
                dfs(i,visited,st,ad);
            }
        }
        st.push(node);
    }
}