My Java Solution, Typical Topology Ordering with comments


  • -1
    X
    public class Solution {
        public class Course implements Comparable<Course> {
            int index;
            ArrayList<Course> dependents;
            int visitState; // -1 not visited, 0 visiting, 1: visited;
            int topOrder; // Save Topology Order
            public Course(int i) {
                index = i;
                dependents = new ArrayList<Course>();
                visitState = -1;
                topOrder = -1;
            }
            // Util functions
            public void addDependent(Course d) {
                dependents.add(d);
            }
            
            public ArrayList<Course> getDependents() {
                return dependents;
            }
            
            public int getIndex() {
                return index;
            }
            
            @Override
            public int compareTo(Course otherCourse) {
                return this.topOrder - otherCourse.topOrder;
            }
        }
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            HashMap<Integer, Course> courses = new HashMap<Integer, Course>();
            for(int i = 0; i < numCourses; i++) {
                courses.put(i, new Course(i));
            }
            
            int m = prerequisites.length;
            // Edge case
            if (m == 0) {
                int[] result = new int[numCourses];
                for(int i = 0; i < numCourses; i++) {
                    result[i] = i;
                }
                return result;
            }
            
            // Normal Case: add prerequisites into Edges
            for(int j = 0; j < m; j++) {
                int preIndex = prerequisites[j][1];
                int depIndex = prerequisites[j][0];
                Course pre = courses.get(preIndex);
                Course dep = courses.get(depIndex);
                pre.addDependent(dep);
            }
            
            int[] availableOrder = new int[1];
            availableOrder[0] = numCourses-1;
           // Do topology ordering on the courses
            while(findUnvisitedCourse(courses)!=null) {
              boolean isValid = dfs(findUnvisitedCourse(courses), availableOrder);
              if (!isValid) {
                  int[] emptyResult = new int[0];
                  return emptyResult;
              }
            }
            
            ArrayList<Course> courseArray = new ArrayList<Course>(courses.values());
            Collections.sort(courseArray);
            int[] finalResult = new int[numCourses];
            for(int i = 0; i < numCourses; i++) {
                finalResult[i] = courseArray.get(i).getIndex();
            }
            return finalResult;
        }
        
        public Course findUnvisitedCourse(HashMap<Integer, Course> courses) {
            ArrayList<Course> courseArray = new ArrayList<Course>(courses.values());
            for(Course c: courseArray) {
                if (c.visitState == -1) {
                    return c;
                }
            }
            return null;
        }
        
        public boolean dfs(Course c, int[] availableOrder) {
            // If the node is already visited, don't bother to loop deeper
            if (c.visitState == 1) {
                return true;
            }
            // If the node is undering exploring, it means a loop is formed and mark it false;
            if (c.visitState == 0) {
                return false;
            }
            // Start visiting the node
            c.visitState = 0;
            for(Course cc: c.getDependents()) {
                boolean isValid = dfs(cc, availableOrder);
                if (!isValid) return false;
            }
            // Done expoloring, mark it visited and give it the top order, available order --
            c.visitState = 1;
            c.topOrder = availableOrder[0];
            availableOrder[0] = availableOrder[0] - 1;
            return true;
        }
    }

Log in to reply
 

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