Course Schedule

题目地址：
https://leetcode.com/problems/course-schedule/description/

题目：

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

解题思路：
这道题可以用dfs，也可以用bfs，但是dfs的最坏情况可能达到V*E，而dfs得最差情况是V + E，所以这道题用bfs来解相对较好。

代码：

dfs 1:

// dfs version -> TLE    any improvement?public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(numCourses == 0 || prerequisites == null){
        return false;
    }
    if(numCourses == 1 && prerequisites.length == 0){
        return true;
    }
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for(int i = 0 ; i <= numCourses - 1; i++){
        graph.put(i, new HashSet<>());
    }
    // put prerequisite into the graph    for(int i = 0; i <= prerequisites.length - 1; i++){
        int curr = prerequisites[i][0];
        int pre = prerequisites[i][1];
        graph.get(curr).add(pre);
    }
    boolean[] visited = new boolean[numCourses];
    int[] rst = new int[numCourses];
    for(int i = 0; i <= numCourses - 1; i++){
        if(graph.get(i).size() == 0){
            rst[i] = 1;
            boolean temp = dfs(graph, visited, rst, numCourses, i);
            if(!temp){
                return false;
            }
        }
    }
    int count = 0;
    for(int i = 0; i <= numCourses - 1; i++){
        if(rst[i] == 1){
            count++;
        }
    }
    return count == numCourses;
}

// if we do not find cycle in dfs when we start from course without prerequisite, and the totoal # is numCourse, it is validprivate boolean dfs(Map<Integer, Set<Integer>> graph, boolean[] visited, int [] rst, int n, int pre) {
    if(visited[pre]){
        return false;
    }
    visited[pre] = true;
    for(int i = 0; i <= n - 1; i++){
        if(graph.get(i).contains(pre)){
            graph.get(i).remove(pre);
            rst[i] = 1;
            boolean temp = dfs(graph, visited, rst, n, i);
            if(!temp){
                return false;
            }
        }
    }
    visited[pre] = false;
    return true;
}

dfs 2 get TLE:

// improvement -> use an array to record the number of prerequisite that this course needpublic boolean canFinish(int numCourses, int[][] prerequisites) {
    if(numCourses == 0 || prerequisites == null){
        return false;
    }
    if(numCourses == 1 && prerequisites.length == 0){
        return true;
    }
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for(int i = 0 ; i <= numCourses - 1; i++){
        graph.put(i, new HashSet<>());
    }
    // put prerequisite into the graph    for(int i = 0; i <= prerequisites.length - 1; i++){
        int curr = prerequisites[i][0];
        int pre = prerequisites[i][1];
        graph.get(curr).add(pre);
    }
    boolean[] path = new boolean[numCourses];
    int[] record = new int[numCourses];

    // update the rst array    for(int curr : graph.keySet()){
        record[curr] = graph.get(curr).size();
    }
    for(int i = 0; i <= numCourses - 1; i++){
        if(graph.get(i).size() == 0){
            boolean temp = dfs(graph, path, record, numCourses, i);
            if(!temp){
                return false;
            }
        }
    }
    int count = 0;
    for(int i = 0; i <= numCourses - 1; i++){
        if(record[i] == 0){
            count++;
        }
    }
    return count == numCourses;
}

// if we do not find cycle in dfs when we start from course without prerequisite, and the totoal # is numCourse, it is validprivate boolean dfs(Map<Integer, Set<Integer>> graph, boolean[] visited, int [] record, int n, int pre) {
    if(visited[pre]){
        return false;
    }
    visited[pre] = true;
    for(int i = 0; i <= n - 1; i++){
        if(graph.get(i).contains(pre) && record[i] != 0){
            record[i] = Math.max(0, record[i] - 1);
            boolean temp = dfs(graph, visited, record, n, i);
            if(!temp){
                return false;
            }
        }
    }
    visited[pre] = false;
    return true;
}

bfs:

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(numCourses == 0 || prerequisites == null){
        return false;
    }
    if(numCourses == 1 && prerequisites.length == 0){
        return true;
    }
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for(int i = 0 ; i <= numCourses - 1; i++){
        graph.put(i, new HashSet<>());
    }
    // put prerequisite into the graph    for(int i = 0; i <= prerequisites.length - 1; i++){
        int curr = prerequisites[i][0];
        int pre = prerequisites[i][1];
        graph.get(curr).add(pre);
    }
    int[] record = new int[numCourses];

    // update the rst array    for(int curr : graph.keySet()){
        record[curr] = graph.get(curr).size();
    }

    Queue<Integer> queue = new LinkedList<>();
    for(int i = 0; i <= numCourses - 1; i++){
        if(graph.get(i). size() == 0){
            queue.offer(i);
        }
    }

    // start bfs here    while(!queue.isEmpty()){
        int pre = queue.poll();
        for(int i = 0; i <= numCourses - 1; i++){
            if(graph.get(i).contains(pre)){
                graph.get(i).remove(pre);
                if(graph.get(i).size() == 0){
                    record[i] = 0;
                    queue.offer(i);
                }
            }
        }
    }
    int count = 0;
    for(int i = 0; i <= numCourses - 1; i++){
        if(record[i] == 0){
            count++;
        }
    }
    return count == numCourses;
}

Follow up:

我可以用一个map来记录从某点可以走到的所有点。例如0->1, 0 -> 2, 1 -> 2, 那么map中就是
<0, <1, 2>>, <1, 2>, 如果来了一个2-> 0, 那么可以在该map中直接找，如果有0->2的路径，那么返回false；如果来了一个valid，那么更新map即可，因为你知道任意一点可以走到的做有点。