课程表

题目描述

给定课程数量与先修关系，如果所有课程都能顺利修完，则返回 true，否则返回 false。

解题思路

建立有向图并进行拓扑排序。若遍历过程中存在入度不为 0 的节点，则说明存在环，课程无法全部完成。

示例输入/输出

输入： numCourses = 2, prerequisites = [[1,0]]

输出： true

代码示例

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = Array(numCourses).fill(0);
  prerequisites.forEach(([a, b]) => {
    graph[b].push(a);
    indegree[a] += 1;
  });
  const queue = [];
  indegree.forEach((value, index) => value === 0 && queue.push(index));
  let count = 0;
  while (queue.length) {
    const node = queue.shift();
    count += 1;
    graph[node].forEach((next) => {
      indegree[next] -= 1;
      if (indegree[next] === 0) queue.push(next);
    });
  }
  return count === numCourses;
}

class Solution {
  public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] edge : prerequisites) {
      graph[edge[1]].add(edge[0]);
      indegree[edge[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.add(i);
    int count = 0;
    while (!queue.isEmpty()) {
      int node = queue.poll();
      count++;
      for (int next : graph[node]) {
        indegree[next]--;
        if (indegree[next] == 0) queue.add(next);
      }
    }
    return count == numCourses;
  }
}

class Solution {
public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> indegree(numCourses, 0);
    for (const auto& edge : prerequisites) {
      graph[edge[1]].push_back(edge[0]);
      ++indegree[edge[0]];
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) if (indegree[i] == 0) q.push(i);
    int count = 0;
    while (!q.empty()) {
      int node = q.front(); q.pop();
      ++count;
      for (int next : graph[node]) {
        --indegree[next];
        if (indegree[next] == 0) q.push(next);
      }
    }
    return count == numCourses;
  }
};

from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    queue = deque(i for i, v in enumerate(indegree) if v == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for next_node in graph[node]:
            indegree[next_node] -= 1
            if indegree[next_node] == 0:
                queue.append(next_node)
    return count == num_courses

numCourses = 2, prerequisites = [[1,0]]

true