JAVA topological sort solution with DFS and Stack


  • 0
    C
    public class Solution {
        
        private Stack<Integer> stack = new Stack<Integer>();
        private ArrayList<ArrayList<Integer>> x = new ArrayList<ArrayList<Integer>>();
    
        
        public int[] findOrder(int numCourses, int[][] prerequisites)
        {
            
            for(int i = 0; i < numCourses; i++)
            {
                x.add(new ArrayList<Integer>());
            }
            
            for(int j = 0; j < prerequisites.length; j++)
            {
                int f = prerequisites[j][0];
                int s = prerequisites[j][1];
                
                x.get(s).add(f);
            }
            
            boolean[] visited = new boolean[numCourses];
            
            for(int i = 0; i < numCourses; i++)
            {
                if(!visited[i])
                {
                    boolean result = dfsWithCycle(i, new ArrayList<Integer>(), visited);
                    if(!result)
                    {
                        return new int[0];
                    }
                }
            }
            
            int[] finalOrder = new int[numCourses];
            
            for(int i = 0; i < numCourses; i++)
            {
                finalOrder[i] = stack.pop();
            }
            
            return finalOrder;
            
            
        }
        
        public boolean dfsWithCycle(int v, ArrayList<Integer> prefix, boolean[] visited)
        {
            for(int i = 0; i < x.get(v).size(); i++)
            {
                if(!(prefix.contains(x.get(v).get(i))))
                {
                    if(!visited[x.get(v).get(i)])
                    {
                        ArrayList<Integer> newPrefix = new ArrayList<Integer>();
                        newPrefix.addAll(prefix);
                        newPrefix.add(v);
                        
                        boolean a = dfsWithCycle(x.get(v).get(i), newPrefix, visited);
                        
                        if(!a)
                        {
                            return a;
                        }
                    }
                }
                else
                {
                    return false;
                }
            }
            
            visited[v] = true;
            stack.push(v);
            
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.