CourseSchedule&CourseSchedule2

https://leetcode.com/problems/course-schedule-ii/
课程之间有依赖,CourseSchedule要求判断是否存在循环依赖,CourseSchedule2要求找出完成课程的路径.
使用Topological sort即可.
CourseSchedule解法来源于https://en.wikipedia.org/wiki/Topological_sorting TopologicalSort based on DFS.

public class CourseSchedule {
    private boolean isDAG = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adjacencyMap = new HashMap();
        Map<Integer, String> markMap = new HashMap();
        for(int i = 0; i < prerequisites.length; i++){
            if(adjacencyMap.containsKey(prerequisites[i][0])){
                adjacencyMap.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }else{
                List<Integer> neighbors = new ArrayList();
                neighbors.add(prerequisites[i][1]);
                adjacencyMap.put(prerequisites[i][0], neighbors);
            }
        }

        for(Map.Entry<Integer, List<Integer>> entry : adjacencyMap.entrySet()){
            Integer course = entry.getKey();
            if(isDAG){
                visit(course, adjacencyMap, markMap);
            }else{
                break;
            }
        }
        return isDAG;
    }

    private void visit(Integer course, Map<Integer, List<Integer>> adjacencyMap, Map<Integer, String> markMap){
        if("0".equals(markMap.get(course))){
            isDAG = false;
            return;
        }
        if("1".equals(markMap.get(course))){
            return;
        }
        markMap.put(course, "0");
        List<Integer> adjacencyList = adjacencyMap.get(course);
        for(Integer dep : adjacencyList){
            if(isDAG){
                visit(dep, adjacencyMap, markMap);
            }else{
                break;
            }
        }
        markMap.put(course, "1");
        return;
    }
}

CourseSchedule2方法和CourseSchedule一样,不过更好理解.

public class CourseSchedule2 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adjacencyMap = new HashMap();

        Map<Integer, Integer> edgeNumMap = new HashMap();
        for(int i = 0 ; i < prerequisites.length; i++){
            List<Integer> adjacencyList = adjacencyMap.getOrDefault(prerequisites[i][0], new ArrayList());
            adjacencyList.add(prerequisites[i][1]);
            adjacencyMap.put(prerequisites[i][0], adjacencyList);
            edgeNumMap.put(prerequisites[i][1], edgeNumMap.getOrDefault(prerequisites[i][1], 0) + 1);
        }

        for(int i = 0; i < numCourses; i++){
            if(!adjacencyMap.containsKey(i)){
                adjacencyMap.put(i, new ArrayList());
            }
            if(!edgeNumMap.containsKey(i)){
                edgeNumMap.put(i, 0);
            }
        }
        List<Integer> coursePath = new ArrayList();
        Deque<Integer> stack = new ArrayDeque();
        for(Map.Entry<Integer, Integer> entry : edgeNumMap.entrySet()){
            if(entry.getValue() == 0){
                stack.offerLast(entry.getKey());
            }
        }

        Set<Integer> visited = new HashSet();

        while(!stack.isEmpty()){
            Integer course = stack.pollFirst();
            visited.add(course);
            coursePath.add(course);
            for(Integer depCourse : adjacencyMap.get(course)){
                edgeNumMap.put(depCourse, edgeNumMap.get(depCourse) - 1);
                if(edgeNumMap.get(depCourse) == 0){
                    if(!visited.contains(depCourse)){
                        stack.offerFirst(depCourse);
                    }
                }
            }
        }
        for(Map.Entry<Integer, Integer> entry : edgeNumMap.entrySet()){
            if(entry.getValue() != 0){
                return new int[0];
            }
        }
        int[] result = new int[coursePath.size()];
        for(int i = 0; i < coursePath.size(); i++){
            result[i] = coursePath.get(coursePath.size() - i - 1);
        }
        return result;
    }
}