LeetCode - 207 课程表

题目来源

207. 课程表 - 力扣（LeetCode）

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例

提示

• 1 <= numCourses <= 10^5
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

题目解析

我们可以根据题目要求画出一个有向图，比如下面用例

numCourses = 4, prerequisites = [[2,1], [4,3], [4,2]]

学2之前，必须先学1；

学4之前，必须先学2，3

学1，3没有前置课程。

因此，通过上面有向图，我们可以得出，能够学完所有课程。

而上面有向图其实就是一种拓扑结构，在拓扑结构中，每一个顶点都有“入度”概念，所谓入度，即当前顶点的直接前驱顶点数目

如上图所示，

顶点1的入度为0

顶点2的入度为1

顶点3的入度为0

顶点4的入度为2，注意入度指的是当前顶点的直接前驱顶点个数，而顶点4的直接前驱只有2，3，因此顶点4的入度为2 。

因此，在处理以上拓扑结构时，我们的入手点，就是入度为0的顶点。

我们假设一个顶点入度为0，表示已经读完了该课程，因此我们假设去掉该顶点，则剩余顶点的入度需要被更新，如下图，1，3顶点被去除后，2的入度更新为0，4的入度更新为1

因此，我们可能又会得到一批新的入度为0的顶点，然后重复以上步骤，直到没有入度为0的顶点，此时，若拓扑结构中，没有残留顶点，则说明，所有课程已经被读完，否则说明无法读完所有课程，比如下面用例

numCourses = 4, prerequisites = [[2,1], [3,2], [4,3], [2,4]]

 

当我们去除一个入度为0的顶点后，剩余顶点的入度没有为0的了，因此无法再去除顶点了，此时出现了环。 

在了解了拓扑排序的基本知识后，我们就可以考虑如何实现以上过程：

首先，我们需要记录每一个顶点的入度，即每一个顶点的直接前驱的个数

然后，我们还需要记录每一个顶点A的直接后继顶点，因为，当顶点A的入度变为0时，模拟去除顶点A，即将顶点A的直接后继顶点们的入度减去1。

在统计完以上信息后，我们就可以遍历所有顶点，找到入度为0的，作为入口条件，运行减度逻辑。

JS算法源码

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const next = {};
 
  // 要想学习a，先要学习b
  for (let [a, b] of prerequisites) {
    // a的入度+1
    inDegree[a]++;
 
    // b的后继节点集合添加a
    next[b] ? next[b].push(a) : (next[b] = [a]);
  }
 
  // 记录入度为0的点
  const queue = [];
 
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
 
  // 记录已完成的课程数目
  let complete = 0;
 
  while (queue.length > 0) {
    // 父课程完成
    const fa = queue.shift();
    complete++;
 
    next[fa]?.forEach((ch) => {
      // 父课程完成后，其后的子课程入度-1
      inDegree[ch] -= 1;
 
      // 如果子课程入度减少为0，则加入队列
      if (inDegree[ch] == 0) {
        queue.push(ch);
      }
    });
  }
 
  // 如果已学完的课程数等于总课程数，表示已经学完
  return complete === numCourses;
};

Java算法源码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
 
class Solution {
  public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    HashMap> next = new HashMap<>();
 
    for (int[] prerequisite : prerequisites) {
      // 要想学习a，先要学习b
      int a = prerequisite[0];
      int b = prerequisite[1];
 
      // a的入度+1
      inDegree[a]++;
 
      // b的后继节点集合添加a
      next.putIfAbsent(b, new ArrayList<>());
      next.get(b).add(a);
    }
 
    // 记录入度为0的点
    LinkedList queue = new LinkedList<>();
 
    for (int i = 0; i < numCourses; i++) {
      if (inDegree[i] == 0) {
        queue.add(i);
      }
    }
 
    // 记录已完成的课程数目
    int complete = 0;
 
    while (queue.size() > 0) {
      // 父课程完成
      int fa = queue.removeFirst();
      complete += 1;
 
      if (next.containsKey(fa)) {
        for (int ch : next.get(fa)) {
          // 父课程完成后，其后的子课程入度-1
          inDegree[ch] -= 1;
 
          // 如果子课程入度减少为0，则加入队列
          if (inDegree[ch] == 0) {
            queue.add(ch);
          }
        }
      }
    }
 
    return complete == numCourses;
  }
}

Python算法源码

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        inDegree = [0] * numCourses
        next = {}
 
        # 要想学习a，先要学习b
        for a, b in prerequisites:
            # a的入度+1
            inDegree[a] += 1
 
            # b的后继节点集合添加a
            next.setdefault(b, [])
            next.get(b).append(a)
 
        # 记录入度为0的点
        queue = []
        for i in range(numCourses):
            if inDegree[i] == 0:
                queue.append(i)
 
        # 记录已完成的课程数目
        complete = 0
 
        while len(queue) > 0:
            # 父课程完成
            fa = queue.pop(0)
            complete += 1
 
            if next.get(fa):
                for ch in next[fa]:
                    # 父课程完成后，其后的子课程入度-1
                    inDegree[ch] -= 1
 
                    # 如果子课程入度减少为0，则加入队列
                    if inDegree[ch] == 0:
                        queue.append(ch)
 
        # 如果已学完的课程数等于总课程数，表示已经学完
        return complete == numCourses

C算法源码

typedef struct Node {
    int ele;
    struct Node *prev;
    struct Node *next;
} ListNode;
 
typedef struct {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;
 
LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}
 
void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;
 
    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }
 
    link->size++;
}
 
int removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);
 
    ListNode *removed = link->head;
 
    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
        link->head->prev = NULL;
    }
 
    link->size--;
 
    return removed->ele;
}
 
bool canFinish(int numCourses, int **prerequisites, int prerequisitesSize, int *prerequisitesColSize) {
    int inDegree[2000] = {0};
    LinkedList *next[2000] = {NULL};
 
    for (int i = 0; i < prerequisitesSize; i++) {
        // 要想学习a，先要学习b
        int a = prerequisites[i][0];
        int b = prerequisites[i][1];
 
        // a的入度+1
        inDegree[a]++;
 
        // b的后继节点集合添加a
        if (next[b] == NULL) {
            next[b] = new_LinkedList();
        }
        addLast_LinkedList(next[b], a);
    }
 
    // 记录入度为0的点
    LinkedList *queue = new_LinkedList();
 
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            addLast_LinkedList(queue, i);
        }
    }
 
    // 记录已完成的课程数目
    int complete = 0;
 
    while (queue->size > 0) {
        // 父课程完成
        int fa = removeFirst_LinkedList(queue);
        complete += 1;
 
        if (next[fa] != NULL) {
            ListNode *cur = next[fa]->head;
 
            while (cur != NULL) {
                int ch = cur->ele;
 
                // 父课程完成后，其后的子课程入度-1
                inDegree[ch] -= 1;
 
                // 如果子课程入度减少为0，则加入队列
                if (inDegree[ch] == 0) {
                    addLast_LinkedList(queue, ch);
                }
 
                // 如果已学完的课程数等于总课程数，表示已经学完
                cur = cur->next;
            }
        }
    }
 
    return complete == numCourses;
}