Сложность: 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 {
static int WHITE = 1;
static int GRAY = 2;
static int BLACK = 3;
boolean isPossible;
Map<Integer, Integer> color;
Map<Integer, List<Integer>> adjList;
List<Integer> topologicalOrder;
private void init(int numCourses) {
this.isPossible = true;
this.color = new HashMap<>();
this.adjList = new HashMap<>();
this.topologicalOrder = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
this.color.put(i, WHITE);
}
}
private void dfs(int node) {
if (!this.isPossible) return;
this.color.put(node, GRAY);
for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<>())) {
if (this.color.get(neighbor) == WHITE) {
this.dfs(neighbor);
} else if (this.color.get(neighbor) == GRAY) {
this.isPossible = false;
}
}
this.color.put(node, BLACK);
this.topologicalOrder.add(node);
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
this.init(numCourses);
for (int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
int src = prerequisites[i][1];
List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
lst.add(dest);
adjList.put(src, lst);
}
for (int i = 0; i < numCourses; i++) {
if (this.color.get(i) == WHITE) {
this.dfs(i);
}
}
if (this.isPossible) {
int[] order = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
order[i] = this.topologicalOrder.get(numCourses - i - 1);
}
return order;
} else {
return new int[0];
}
}
}Ставь 👍 и забирай 📚 Базу знаний