Leetcode #207 Course Schedule

[yokostan]

Map & indegree map, runtime beats 38%:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];

    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }

    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}
}

Adjacent map, beat 84%:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 0: init, 1: ongoing recursion, 2: done
        int[] status = new int[numCourses];
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>(); // adjacency list
        for (int[] pre : prerequisites) {
            if (!graph.containsKey(pre[1])) 
                graph.put(pre[1], new ArrayList<Integer>());
            graph.get(pre[1]).add(pre[0]);
        }
        for (int c = 0; c < numCourses; c++) {
            if (!dfs(c, graph, status)) return false;
        }
        return true;
    }
    private boolean dfs(int course, HashMap<Integer, ArrayList<Integer>> graph, int[] status) {
        if (status[course] == 2) return true;
        if (status[course] == 1) return false;
        status[course] = 1;
        if (graph.containsKey(course)) {
            for (int c : graph.get(course)) {
                if (!dfs(c, graph, status)) return false;
            }
        }
        status[course] = 2;
        return true;
    }
}

Regular map beats 55%:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 0: init, 1: ongoing recursion, 2: done
        int[] status = new int[numCourses];
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>(); // adjacency list
        for (int[] pre : prerequisites) {
            if (!graph.containsKey(pre[1])) 
                graph.put(pre[1], new ArrayList<Integer>());
            graph.get(pre[1]).add(pre[0]);
        }
        for (int c = 0; c < numCourses; c++) {
            if (!dfs(c, graph, status)) return false;
        }
        return true;
    }
    private boolean dfs(int course, HashMap<Integer, ArrayList<Integer>> graph, int[] status) {
        if (status[course] == 2) return true;
        if (status[course] == 1) return false;
        status[course] = 1;
        if (graph.containsKey(course)) {
            for (int c : graph.get(course)) {
                if (!dfs(c, graph, status)) return false;
            }
        }
        status[course] = 2;
        return true;
    }
}public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // write your code here
        // 已知node和edge构造存储有向图图的map
        // 有了map之后，剩下的解法类似于topological sorting 那道题
        // 思路：1.把输入的参数转换成map形式存储的图
        // 2.拓扑排序得到list of result
        // 3.判断list中的节点个数是否为numCourses
        // 因为拓扑排序节点入度为0时才会存入result
        // 所以如果存在环，那么有向图的拓扑排序节点个数就会小于图的节点个数
        if (numCourses == 0 || prerequisites.length == 0) {
            return true;
        }

        //创建courseMap
        HashMap<Integer, List<Integer>> courseMap = creatCourseMap(numCourses, prerequisites);
        //统计各个节点的入度
        HashMap<Integer, Integer> indegreeMap = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            for (Integer neighbor : courseMap.get(i)) {
                if (indegreeMap.containsKey(neighbor)) {
                    indegreeMap.put(neighbor, indegreeMap.get(neighbor) + 1);
                } else {
                    indegreeMap.put(neighbor, 1);
                }
            }
        }

        // 把所有入度为0的点，放到BFS专用的队列中
        Queue<Integer> queue = new LinkedList<>();
        // 初始化拓扑序列为空
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!indegreeMap.containsKey(i)) {
                queue.offer(i);
                result.add(i);
            }
        }

        // 每次从队列中拿出一个点放到拓扑序列里，并将该点指向的所有点的入度减1
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            for (Integer neighbor : courseMap.get(course)) {
                indegreeMap.put(neighbor, indegreeMap.get(neighbor) - 1);
                // 减去1之后入度变为0的点，也放入队列
                if (indegreeMap.get(neighbor) == 0) {
                    queue.offer(neighbor);
                    result.add(neighbor);
                }
            }
        }
        // 判断拓扑排序数与图的节点数是否相同
        return result.size() == numCourses;
    }

    //创建courseMap有向图,方向为先修课程指向当前课程pre -> sou
    private HashMap<Integer, List<Integer>> creatCourseMap(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            map.get(pre).add(cur);
        }
        return map;
    }
}

[yokostan]

Explanation for DFS adjacent map: In DFS, the general idea, is to search each vertex in the graph recursively, if the current vertex has been visited in this search, then there must be a cycle. Be careful with the status of each vertex, here in my code, it has three states: unvisited (=0), visiting(=1), visited(=2). The =1 state is to detect the existence of cycle, while the =2 state indicate that the vertex is already checked and there is no cycle.

[yokostan]

Think about it like a forest, 2 means all elements that we could possibly reach in this tree has been visited and whenever we find another prerequisite course that leads to this tree, then it's fine. But if we are checking a tree with status 1 and have found duplicate element, then this tree is not gonna work.