Course Schedule
Leetcode #207 | Medium | Топологическая сортировка | BFS | Очередь
Идея
Заводим массив счетчиков зависимостей (сколько нужно пройти курсов для прохождения i-го), заводим мапу курс->лист курсов, которые открываются после прохождения. Дальше заводим счетчик пройденных курсов и очередь. Наполняем очередь курсами с нулями зависимостей - их можно пройти прям сейчас. Дальше итерируемся по очереди. Достали курс, прибавили пройденные, если от этого курса что-то зависит то идем по этим зависящим курсам, уменьшаем их зависимость и если они стали доступными дял прохождения - добавляем в очередь
Big-O
- Время
O(V+E) - Память
O(V+E)
Код
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
Map<Integer, List<Integer>> graph = new HashMap<>();
int completeCourseCount = 0;
for (int i = 0; i < prerequisites.length; i++) {
int depend = prerequisites[i][0];
int prereq = prerequisites[i][1];
if (!graph.containsKey(prereq)) {
graph.put(prereq, new ArrayList<Integer>());
}
graph.get(prereq).add(depend);
indegrees[depend]++;
}
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
queue.offer(i);
}
}
while (queue.size() > 0) {
int course = queue.poll();
completeCourseCount++;
if (!graph.containsKey(course)) {
continue;
}
for (int dependCourse: graph.get(course)) {
indegrees[dependCourse]--;
if (indegrees[dependCourse] == 0) {
queue.offer(dependCourse);
}
}
}
return completeCourseCount == numCourses;
}
}