Задача: 1136. Parallel Courses
Сложность: 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 {
    func minimumSemesters(_ N: Int, _ relations: [[Int]]) -> Int {
        var graph = [[Int]](repeating: [], count: N + 1)
        for relation in relations {
            graph[relation[0]].append(relation[1])
        }
        
        var visited = [Int](repeating: 0, count: N + 1)
        for node in 1...N {
            if dfsCheckCycle(node, graph, &visited) == -1 {
                return -1
            }
        }

        var visitedLength = [Int](repeating: 0, count: N + 1)
        var maxLength = 1
        for node in 1...N {
            let length = dfsMaxPath(node, graph, &visitedLength)
            maxLength = max(length, maxLength)
        }
        return maxLength
    }

    private func dfsCheckCycle(_ node: Int, _ graph: [[Int]], _ visited: inout [Int]) -> Int {
        if visited[node] != 0 {
            return visited[node]
        } else {
            visited[node] = -1
        }
        for endNode in graph[node] {
            if dfsCheckCycle(endNode, graph, &visited) == -1 {
                return -1
            }
        }
        visited[node] = 1
        return 1
    }

    private func dfsMaxPath(_ node: Int, _ graph: [[Int]], _ visitedLength: inout [Int]) -> Int {
        if visitedLength[node] != 0 {
            return visitedLength[node]
        }
        var maxLength = 1
        for endNode in graph[node] {
            let length = dfsMaxPath(endNode, graph, &visitedLength)
            maxLength = max(length + 1, maxLength)
        }
        visitedLength[node] = maxLength
        return maxLength
    }
}

Ставь 👍 и забирай 📚 Базу знаний