Сложность: medium
Вам дано целое число n, которое указывает, что есть n курсов, обозначенных от 1 до n. Вам также дан массив relations, где relations[i] = [prevCoursei, nextCoursei], представляющий собой зависимость между курсами: курс prevCoursei должен быть пройден до курса nextCoursei.
За один семестр вы можете взять любое количество курсов, при условии, что вы прошли все необходимые предварительные курсы в предыдущем семестре для тех курсов, которые вы собираетесь взять.
Верните минимальное количество семестров, необходимых для прохождения всех курсов. Если нет способа пройти все курсы, верните -1.
Пример:
Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.
👨💻 Алгоритм:
1⃣Постройте направленный граф из зависимостей (relations).
2⃣Реализуйте функцию dfsCheckCycle для проверки наличия цикла в графе.
3⃣Реализуйте функцию dfsMaxPath для вычисления длины самого длинного пути в графе. Если цикл найден, верните -1. Иначе верните длину самого длинного пути.
😎 Решение:
class Solution:
def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
graph = [[] for _ in range(N + 1)]
for prev, next in relations:
graph[prev].append(next)
visited = [0] * (N + 1)
for node in range(1, N + 1):
if self.dfsCheckCycle(node, graph, visited) == -1:
return -1
visited_length = [0] * (N + 1)
max_length = 1
for node in range(1, N + 1):
length = self.dfsMaxPath(node, graph, visited_length)
max_length = max(length, max_length)
return max_length
def dfsCheckCycle(self, node, graph, visited):
if visited[node] != 0:
return visited[node]
else:
visited[node] = -1
for end_node in graph[node]:
if self.dfsCheckCycle(end_node, graph, visited) == -1:
return -1
visited[node] = 1
return 1
def dfsMaxPath(self, node, graph, visited_length):
if visited_length[node] != 0:
return visited_length[node]
max_length = 1
for end_node in graph[node]:
length = self.dfsMaxPath(end_node, graph, visited_length)
max_length = max(length + 1, max_length)
visited_length[node] = max_length
return max_length
Ставь 👍 и забирай 📚 Базу знаний