Сложность: medium
Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.
Пример:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].
👨💻 Алгоритм:
1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.
2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.
3⃣Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.
😎 Решение:
class Solution {
companion object {
const val WHITE = 1
const val GRAY = 2
const val BLACK = 3
}
private var isPossible: Boolean = true
private lateinit var color: MutableMap<Int, Int>
private val adjList: MutableMap<Int, MutableList<Int>> = HashMap()
private val topologicalOrder: MutableList<Int> = ArrayList()
private fun init(numCourses: Int) {
isPossible = true
color = HashMap()
adjList.clear()
topologicalOrder.clear()
for (i in 0 until numCourses) {
color[i] = WHITE
}
}
private fun dfs(node: Int) {
if (!isPossible) return
color[node] = GRAY
for (neighbor in adjList.getOrDefault(node, mutableListOf())) {
when (color[neighbor]) {
WHITE -> dfs(neighbor)
GRAY -> isPossible = false
}
}
color[node] = BLACK
topologicalOrder.add(node)
}
fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
init(numCourses)
for (prerequisite in prerequisites) {
val (dest, src) = prerequisite
adjList.computeIfAbsent(src) { mutableListOf() }.add(dest)
}
for (i in 0 until numCourses) {
if (color[i] == WHITE) {
dfs(i)
}
}
return if (isPossible) {
val order = IntArray(numCourses)
for (i in 0 until numCourses) {
order[i] = topologicalOrder[numCourses - i - 1]
}
order
} else {
intArrayOf()
}
}
}Ставь 👍 и забирай 📚 Базу знаний