Skip to content

207. Course Schedule

🔗 Source

Intuition

We traverse the graph and find if there is a topological

Approach

  • Create a 1-d array visit to record the visit status, with 3 states:
    • 0 means it has not been visited
    • 1 means it has been visited
    • -1 means there is a conflict
  • Firstly, build a directed graph, and then start from the first course, find which course it can constitute, temporarily mark the current course as visited
  • Call DFS recursion on the newly obtained course until a new course has been visited, then return false, if there is no conflict, return true, and then change the course marked as visited to unvisited.

Complexity

  • Time complexity: \(O(V+E)\)
  • Space complexity: \(O(V)\)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adjcent = new List[numCourses];
        int[] visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adjcent[i] = new ArrayList<>();
        }
        for (int[] pairs : prerequisites) {
            adjcent[pairs[1]].add(pairs[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(adjcent, i, visit)) {
                return false;
            }
        }
        return true;
    }
    private boolean dfs(List<Integer>[] graph, int node, int[] visit) {
        // Set 1: visited
        // Set 0: unvisited
        // Set -1: there is a conflict
        if (visit[node] == 1) {
            return true;
        }

        if (visit[node] == -1) {
            return false;
        }

        visit[node] = -1;
        for (int n : graph[node]) {
            if (!dfs(graph, n, visit)) {
                return false;
            }
        }
        visit[node] = 1;
        return true;
    }
}