Java DFS - typical topological sort


  • 0
    A
    class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // algorithm 2017/08/27: DFS to track the order how we decide whether a course has no other dependency (and no cycle)
        
        if (null == prerequisites || 0 == numCourses) {
            return new int[0];
        }
        
        // assemble inDegrees, and use a hashMap to track dependency
        HashMap<Integer, Set<Integer>> dependencies = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            Set<Integer> dependsOn = dependencies.get(prerequisite[0]);
            if (null == dependsOn) {
                dependsOn = new HashSet<>();
                dependencies.put(prerequisite[0], dependsOn);
            }
            dependsOn.add(prerequisite[1]);
        }
        
        int[] decidedResult  = new int[numCourses];  // 0: not decided, 1: has no cycle; 2: has cycle
        List<Integer> orders = new ArrayList<>();
        boolean hasCycle     = false;
        for (int course = 0; course < numCourses; course++) {
            boolean[] visited = new boolean[numCourses];        // track visisted nodes 
            if (findCycle(dependencies, decidedResult, visited, orders, course)) {
                hasCycle = true;
                break;  // find a cycle, no need to continue
            }
        }
        
        if (hasCycle) {
            return new int[0];
        } else {
            int[] result = new int[numCourses];
            int index    = 0;
            for (int course : orders) {
                result[index++] = course;
            }
            return result;
        }
        
    }
    
    private boolean findCycle(HashMap<Integer, Set<Integer>> dependencies, int[] decidedResult, boolean[] visited, List<Integer> orders, int fromCourse) {
        if (1 == decidedResult[fromCourse]) {
            return false;        // there is no cycle
        } else if (2 == decidedResult[fromCourse]) {
            return true;       // there is a cycle
        }
        
        if (visited[fromCourse]) {
            decidedResult[fromCourse] = 2;
            return true;        // there is a cycle
        }
        visited[fromCourse] = true;
        
        // follow all dependencies in a DFS fashion
        Set<Integer> dependsOn = dependencies.get(fromCourse);
        if (null != dependsOn) {
            for (int dependOn : dependsOn) {
                if (findCycle(dependencies, decidedResult, visited, orders, dependOn)) {
                    decidedResult[fromCourse] = 2;
                    return true;
                }
            }
        }
        visited[fromCourse] = false;
        // no cycle after checking all dependencies
        decidedResult[fromCourse] = 1;
        orders.add(fromCourse);
        return false;
    }
    

    }


Log in to reply
 

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