/ Data Structure and Algorithms  

Leetcode 210: Course Schedule II

Question



A extension on 207. Course Schedule. Given the relationship of n groups of prerequisite courses, [m, n] means that you must take n courses before taking m courses. Output a lesson sequence.

Similar Questions

Solution

207. Course Schedule is to determine whether there is a sequence to finish all the lessons. Here we need to output the sequence. The idea is basically the same.

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.

We can use the outDegree 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.

In the end, it is only necessary to determine whether the number of prerequisite courses of all nodes is all 0.

Just need to modify the code of 207. Course Schedule to record the element that is popped from the queue.

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public int[] findOrder(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 add the course that has 0 out degree to results
    // if there are any course left with non-zero out degree, means we can't finish all courses
    // there might be course that are independent, just add them at the end

    // 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);
        }
    }

    // result list
    List<Integer> results = new ArrayList<>();

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

        // add this course to result list
        results.add(tempCourse);

        // 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);
        }
    }

    // check if all course has 0 prerequisite
    for (Integer course : courses) {
        // this means there are courses that we can't finish
        if (outDegree.getOrDefault(course, 0) != 0) {
            return new int[0];
        }
    }

    // there are courses that are independent (not dependency or prerequisite
    // we can do those courses at any time
    for (int i = 0; i < numCourses; i++) {
        if (!courses.contains(i)) {
            results.add(i);
        }
    }

    return results.stream().mapToInt(i -> i).toArray();
}