Leetcode #207 | #Medium | [[Топологическая сортировка]] | [[BFS]] | [[Очередь]]
## Идея
Заводим массив счетчиков зависимостей (сколько нужно пройти курсов для прохождения i-го), заводим мапу курс->лист курсов, которые открываются после прохождения. Дальше заводим счетчик пройденных курсов и очередь. Наполняем очередь курсами с нулями зависимостей - их можно пройти прям сейчас. Дальше итерируемся по очереди. Достали курс, прибавили пройденные, если от этого курса что-то зависит то идем по этим зависящим курсам, уменьшаем их зависимость и если они стали доступными дял прохождения - добавляем в очередь
## Big-O
- Время ```O(V+E)```
- Память  ```O(V+E)```
## Код
```Java
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;
    }
}
```