Leetcode 210. Course Schedule II

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

Solution

这是一道典型的拓扑排序的题。题目通过课程的依赖关系来描述了整个图的结构。我们用BFS来解决:

  • 我们对入度为0(无前置课程)的节点(课程)开始,将它们加入到一个队列中。
  • 将所有入度为0的节点保存到结果中,并在整个图中删除掉这些节点与他们的出度的边(依赖它们的课程的入度-1),并将入度减过1后等于0的节点再次加入到队列中。
  • 重复上述两步

其实整个过程就是一个不断拆解的过程。

代码如下:

Java

class Solution {
    class Course {
        int index;
        int count;
        List<Course> children;

        public Course() {
            children = new ArrayList<>();
        }
    }
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites == null) return new int[0];
        Course[] courses = new Course[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (courses[i] == null) courses[i] = new Course();
            courses[i].index = i;
        }
        // init graph
        for (int[] edge : prerequisites) {
            courses[edge[0]].count++;
            courses[edge[1]].children.add(courses[edge[0]]);
        }

        List<Integer> res = new ArrayList<>();
        Deque<Course> queue = new LinkedList<>();
        // start bfs, add the node with 0-inDegree
        for (Course course : courses) {
            if (course.count == 0) queue.offer(course);
        }
        while (!queue.isEmpty()) {
            Course cur = queue.pop();
            res.add(cur.index);
            for (Course child : cur.children) {
                // update others node
                if (--child.count == 0)
                    queue.offer(child);
            }

        }
        if (res.size() != numCourses) return new int[0];
        else return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}

Python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        dic = {i : 0 for i in range(numCourses)}
        children = collections.defaultdict(set)
        for i, j in prerequisites:
            dic[i] += 1
            children[j].add(i)

        queue = collections.deque([i for i in dic if dic[i] == 0])
        res = []
        while queue:
            cur = queue.popleft()
            res.append(cur)
            for i in children[cur]:
                dic[i] -= 1
                if dic[i] == 0:
                    queue.append(i)
        return res if len(res) == numCourses else []

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号