207 Course Schedule

207. Course Schedule

1. Question

There are a total ofncourses you have to take, labeled from0ton - 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.

Note:

1. The input prerequisites is a graph represented by a list of edges , not adjacency matrices.

2. You may assume that there are no duplicate edges in the input prerequisites.

2. Implementation

(1) BFS

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            adjList.add(new HashSet<>());
        }

        int[] inDegree = new int[numCourses];

        for (int[] prerequisite : prerequisites) {
            adjList.get(prerequisite[0]).add(prerequisite[1]);
            ++inDegree[prerequisite[1]];
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;

        while (!queue.isEmpty()) {
            int course = queue.remove();
            ++count;

            for (int nextCourse : adjList.get(course)) {
                if (--inDegree[nextCourse] == 0) {
                    queue.add(nextCourse);
                }
            }
        }
        return count == numCourses;
    }
}

(2) DFS

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;

        List<Set<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        for (int[] prerequisite : prerequisites) {
            adjList.get(prerequisite[1]).add(prerequisite[0]);
        }

        boolean[] visited = new boolean[n];
        boolean[] onStack = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (!dfs(i, visited, onStack, adjList)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean dfs(int course, boolean[] visited, boolean[] onStack, List<Set<Integer>> adjList) {
        if (visited[course]) {
            return true;
        }

        if (onStack[course]) {
            return false;
        }

        onStack[course] = true;

        for (int nextCourse : adjList.get(course)) {
            if (!dfs(nextCourse, visited, onStack, adjList)) {
                return false;
            }
        }

        visited[course] = true;
        onStack[course] = false;
        return true;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(n)，空间复杂度O(n)

DFS: 时间复杂度O(n)，空间复杂度O(n)