本文共 1340 字，大约阅读时间需要 4 分钟。

已知有 N 门课程，它们以 1 到 N 进行编号。

给你一份课程关系表 relations[i] = [X, Y]，用以表示课程 X 和课程 Y 之间的先修关系：课程 X 必须在课程 Y 之前修完。

假设在一个学期里，你可以学习任何数量的课程，但前提是你已经学习了将要学习的这些课程的所有先修课程。

请你返回学完全部课程所需的最少学期数。

如果没有办法做到学完全部这些课程的话，就返回 -1。

示例 1：

输入：N = 3, relations = [[1,3],[2,3]]输出：2解释：在第一个学期学习课程 1 和 2，在第二个学期学习课程 3。

示例 2：

输入：N = 3, relations = [[1,2],[2,3],[3,1]]输出：-1解释：没有课程可以学习，因为它们相互依赖。

提示：

1. 1 <= N <= 5000
2. 1 <= relations.length <= 5000
3. relations[i][0] != relations[i][1]
4. 输入中没有重复的关系

解题思路

这是一个拓扑排序的问题，具体可以看。拓扑排序要解决的问题是有向无环图，而对于有环图，必然环内点的入度不为0，那么环内的点就不可以添加到结果数组中去，那么我们最后可以通过结果数组的长度判断所给数组是不是有环。

最少的学期数，也非常简单，就是通过bfs遍历的层数。

class Solution:    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:        g, d = collections.defaultdict(list), [0] * N        for i, j in relations:            g[i - 1].append(j - 1)            d[j - 1] += 1                q, resLen, res = list(), 0, 0        for i in range(N):            if d[i] == 0:                q.append(i)                resLen += 1                while len(q):            n = len(q)            for _ in range(n):                pre = q.pop(0)                for i in g[pre]:                    d[i] -= 1                    if d[i] == 0:                        q.append(i)                        resLen += 1            res += 1                return res if resLen == N else -1

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/97611526 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！