210.课程表II

链接：210.课程表II
难度：Medium
标签：深度优先搜索、广度优先搜索、图、拓扑排序
简介：现在你总共有 n 门课需要选，记为  0  到  n-1。在选修某些课程之前需要一些先修课程。  例如，想要学习课程 0 ，你需要先完成课程  1 ，我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

题解 1 - javascript

• 编辑时间：2020-05-17
• 执行用时：644ms
• 内存消耗：43.5MB
• 编程语言：javascript
• 解法介绍：通过队列出栈无前置课程的课程，依次压栈。

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  const course = [];
  for (let i = 0; i < numCourses; i++) course[i] = new Course(i);
  for (const [next, prev] of prerequisites) {
    course[next].prev.push(course[prev]);
    course[prev].next.push(course[next]);
  }
  const topo = [];
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (!course[i].hasPrev()) queue.push(course[i]);
  let time = 0;
  let max = numCourses * (numCourses - 1);
  while (queue.length !== 0) {
    if (time++ > max) return [];
    const course = queue.shift();
    if (course.hasPrev()) {
      queue.push(course);
      continue;
    }
    topo.push(course);
    if (!course.hasNext()) continue;
    for (const next of course.next) {
      if (!queue.includes(next)) queue.push(next);
      next.prev = next.prev.filter(v => v !== course);
    }
  }
  if (topo.length !== numCourses) return [];
  return topo.map(v => v.val);
};
class Course {
  prev = [];
  next = [];
  constructor(val) {
    this.val = val;
  }
  hasPrev() {
    return this.prev.length !== 0;
  }
  hasNext() {
    return this.next.length !== 0;
  }
}

题解 2 - python

• 编辑时间：2023-09-10
• 执行用时：48ms
• 内存消耗：17.51MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        used_count = 0
        arr = [[set(),set()] for _ in range(numCourses)]
        for [item1, item2] in prerequisites:
            arr[item1][0].add(item2)
            arr[item2][1].add(item1)
        q = [i for i in range(numCourses) if not len(arr[i][0])]
        res = []
        while len(q):
            cur = q.pop()
            res.append(cur)
            for child in arr[cur][1]:
                arr[child][0].remove(cur)
                if not len(arr[child][0]):
                    q.append(child)
        return res if numCourses == len(res) else []