Java OOO using TopologicalSort


  • 0
    T
    
    
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            if (null == prerequisites){
                return new int[0];
            }
    
            Course[] graph = buildGraph(numCourses, prerequisites);
    
            Set<Course> grey = new HashSet<>();
            Set<Course> black = new HashSet<>();
            List<Integer> list = new ArrayList<>();
    
            for (Course course : graph){
                if (null != course) {
                    boolean hasCycles = hasCycles(course, grey, black, list);
                    if (hasCycles) {
                        return new int[0];
                    }
                }
            }
    
            int[] result = new int[list.size()];
    
            int i = 0;
            for (Integer val : list){
                result[i] = val;
                i++;
            }
    
            return result;
        }
    
    
        private boolean hasCycles(Course course, Set<Course> grey, Set<Course> black, List<Integer> list){
            grey.add(course);
    
            for (Course dependent : course.getDependents()){
                if (!black.contains(dependent)){
                    if (grey.contains(dependent)){
                        return true;
                    }
    
                    boolean cycle = hasCycles(dependent, grey, black, list);
                    if (cycle){
                        return true;
                    }
                }
            }
    
    
            grey.remove(course);
    
            if (!black.contains(course)) {
                list.add(course.num);
                black.add(course);
            }
    
            return false;
        }
    
        private Course[] buildGraph(int n, int[][] pre){
            Course[] courses = new Course[n];
            for (int i = 0; i< n; i++){
                courses[i] = new Course(i);
            }
    
            for (int[] row : pre){
                int p = row[0];
                int d = row[1];
    
                Course parent = courses[p];
                Course dependent = courses[d];
                parent.addDependent(dependent);
            }
    
            return courses;
        }
    
        private static class Course{
            int num;
            List<Course> dependent = new ArrayList<>();
    
            public Course(int v){
                num = v;
            }
    
            public void addDependent(Course d){
                dependent.add(d);
            }
    
            public List<Course> getDependents(){
                return dependent;
            }
        }
    
    
    

Log in to reply
 

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