课程表

题解思路

拓扑排序（Kahn 算法，BFS）

适用场景：判断有向图是否有环。

算法步骤：

1. 构建有向图：用 邻接表 记录课程的先修关系，用 入度数组 记录每门课程的前置课程数量。
2. 拓扑排序：
   • 先找到所有 入度为 0 的课程（可以直接学习的课程）。
   • 逐步学习这些课程，并更新它们指向的课程的 入度。
   • 如果最终所有课程都能学习，则返回 true；否则返回 false（存在循环依赖）。

时间复杂度：

• 构建图：$O(m)$，其中 m 为 prerequisites 的长度。
• 拓扑排序：$O(numCourses + m)$。
• 总体复杂度：$O(numCourses + m)$。

代码实现

Python 代码

import sys
from collections import deque

def canFinish(numCourses, prerequisites):
    # 构建邻接表和入度表
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses

    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    # 找到所有入度为 0 的课程
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0  # 记录已修课程数

    while queue:
        course = queue.popleft()
        count += 1  # 学习一门课程
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return count == numCourses

# 读取输入
numCourses = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
prerequisites = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

# 输出结果
print(canFinish(numCourses,prerequisites))

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> in_degree(numCourses, 0);

    for (auto& pre : prerequisites) {
        graph[pre[1]].push_back(pre[0]);
        in_degree[pre[0]]++;
    }

    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (in_degree[i] == 0) q.push(i);
    }

    int count = 0;
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        count++;
        for (int next : graph[course]) {
            if (--in_degree[next] == 0) q.push(next);
        }
    }

    return count == numCourses;
}

int main() {
    int numCourses, m;
    cin >> numCourses >> m;
    vector<vector<int>> prerequisites(m, vector<int>(2));

    for (int i = 0; i < m; i++) {
        cin >> prerequisites[i][0] >> prerequisites[i][1];
    }

    cout << (canFinish(numCourses, prerequisites) ? "true" : "false") << endl;
    return 0;
}

Java 代码

import java.util.*;

public class Main {
    public static 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[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int next : graph.get(course)) {
                if (--inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return count == numCourses;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numCourses = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] prerequisites = new int[m][2];

        for (int i = 0; i < m; i++) {
            prerequisites[i][0] = scanner.nextInt();
            prerequisites[i][1] = scanner.nextInt();
        }

        System.out.println(canFinish(numCourses, prerequisites) ? "true" : "false");
    }
}

Leetcode 53.课程表-原题链接

题目内容

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

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

• 例如，先修课程对 $[0, 1]$ 表示：想要学习课程 $0$，你需要先完成课程 $1$ 。

请你判断是否可能完成所有课程的学习？如果可以，返回 $true$ ；否则，返回 $false$ 。

输入描述

• 第一行输入一个整数 $numCourses$，表示课程总数。
• 第二行输入一个整数 $m$，表示先修课程对的数量。
• 接下来 $m$ 行，每行输入两个整数 $a_i b_i$，表示课程 $a_i$ 需要先修 $b_i$。

输出描述

如果可以完成所有课程的学习，输出 true，否则输出 false。

样例1

输入

2
1
1 0

输出

true

说明

总共有 $2$门课程。学习课程 $1$ 之前，你需要完成课程$0$ 。这是可能的。

样例2

输入

2
2
1 0
0 1

输出

false

说明

总共有 $2$ 门课程。学习课程 $1$之前，你需要先完成课程$0$；并且学习课程$0$之前，你还应先完成课程 $1$ 。这是不可能的。

提示

• $1 <= numCourses <= 2000$
• $0 <= prerequisites.length <= 5000$
• $prerequisites[i].length == 2$
• $0 <= a_i, b_i < numCourses$
• $prerequisites[i]$中的所有课程对互不相同