/ Data Structure and Algorithms  

Leetcode 207. Course Schedule

Question



Given the relationship of n groups of prerequisite courses, [m, n] means that n class must be taken before m class. Output whether a student can successfully complete all classes.

Similar Questions

Solution

All relationships can be regarded as the edges of the graph, and all the edges constitute a directed graph.

For [[1,3], [1,4], [2,4], [3,5], [3,6], [4,6]], it can be seen as the figure below, the arrow points to the prerequisite class.



If we want to finish all the classes, there must be some classes that have no prerequisite, such as 5 and 6 in the picture above. Then we can delete the 5 and 6 nodes.



Then we can take 3 and 4, and 3 and 4 are deleted for the same reason.

Then we can take 1 and 2. Therefore, all classes can be completed.

In terms of codes, the graph is represented by an adjacency list. In addition, we don’t need to actually delete the node, we can use the outNum variable to record the number of prerequisite courses for all nodes. When deleting a node, the number of prerequisite courses of the corresponding node can be reduced by one.

Lastly, we only need to determine the number of prerequisite courses of all nodes is 0.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public static boolean canFinish(int numCourses, int[][] prerequisites) {
    // out degree means the number of prerequisites of this course
    // in degree means the this course is the prerequisites of other courses
    // gradually remove the course that has 0 out degree
    // in the end we should have all course with 0 out degree

    // map courseId -> number of prerequisites
    Map<Integer, Integer> outDegree = new HashMap<>();
    // map courseId -> list of course id that are depend on this course
    Map<Integer, ArrayList<Integer>> inDegree = new HashMap<>();
    // set to store all courseId
    Set<Integer> courses = new HashSet<>();

    for (int[] ints : prerequisites) {
        int course = ints[0];
        int prerequisite = ints[1];

        // update out degree of course
        outDegree.put(course, outDegree.getOrDefault(course, 0) + 1);

        // update in degree of prerequisite
        ArrayList<Integer> tempList = inDegree.getOrDefault(prerequisite, new ArrayList<>());
        tempList.add(course);
        inDegree.put(prerequisite, tempList);

        // add both course to set
        courses.add(course);
        courses.add(prerequisite);
    }

    // now get all courses without any prerequisite
    Queue<Integer> courseWithoutPrerequisite = new LinkedList<>();
    for (Integer course : courses) {
        if (outDegree.getOrDefault(course, 0) == 0) {
            courseWithoutPrerequisite.offer(course);
        }
    }

    while (!courseWithoutPrerequisite.isEmpty()) {
        int tempCourse = courseWithoutPrerequisite.poll();

        // now we want to remove tempCourse from all other course's prerequisite list
        // get the in degree (list) of tempCourse
        // loop through it, reduce the corresponding out degree by 1
        for (int temp : inDegree.getOrDefault(tempCourse, new ArrayList<>())) {
            int num = outDegree.get(temp);

            // if this course only has 1 prerequisite before, now it has 0
            if (num == 1) {
                courseWithoutPrerequisite.offer(temp);
            }

            outDegree.put(temp, num - 1);
        }
    }

    // finally check if all course has 0 prerequisite
    for (Integer course : courses) {
        if (outDegree.getOrDefault(course, 0) != 0) {
            return false;
        }
    }

    return true;
}