1.题目基本信息
1.1.题目描述
给你一个整数 n ，表示编号从 1 到 n 的 n 门课程。另给你一个数组 relations ，其中 relations[i] = [prevCoursei, nextCoursei] ，表示课程 prevCoursei 和课程 nextCoursei 之间存在先修关系：课程 prevCoursei 必须在 nextCoursei 之前修读完成。
在一个学期内，你可以学习 任意数量 的课程，但前提是你已经在 上 一学期修读完待学习课程的所有先修课程。
请你返回学完全部课程所需的 最少 学期数。如果没有办法做到学完全部这些课程的话，就返回 -1。
1.2.题目地址
https://leetcode.cn/problems/parallel-courses/description/
2.解题方法
2.1.解题思路
kahn算法进行拓扑排序
2.2.解题步骤
第一步，构建有向图的邻接表和入度字典
第二步，kahn算法拓扑排序
-
2.1.记录下一层的节点
-
2.2.遍历一层的节点
第三步，根据最终的入度字典判断图中是否存在环，并返回结果
3.解题代码
python代码
from collections import defaultdictclass Solution:# Kahn算法解拓扑def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:# 第一步，构建有向图的邻接表和入度字典graph={i+1:[] for i in range(n)}inDict=defaultdict(int)for edge in relations:graph[edge[0]].append(edge[1])inDict[edge[1]]+=1# print("t1",graph,inDict)# 第二步，kahn算法拓扑排序que=[key for key in graph.keys() if inDict[key]==0]# print("t2",que)cnt=0while que:# 2.1.记录下一层的节点nextSliceNodes=[]# 2.2.遍历一层的节点for node in que:for subNode in graph[node]:inDict[subNode]-=1if inDict[subNode]==0:nextSliceNodes.append(subNode)que=nextSliceNodescnt+=1# 第三步，根据最终的入度字典判断图中是否存在环，并返回结果if sum(inDict.values())!=0:return -1# print("t3",cnt)return cnt
4.执行结果
