🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 210. Course Schedule II
Сложность: medium
Дано число numCourses и список пар prerequisites, где каждая пара [a, b] означает: чтобы взять курс a, нужно сначала пройти курс b.
Верните один из возможных порядков прохождения курсов.
Если пройти все курсы невозможно (из-за циклов) — верните пустой массив.
Пример:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]
👨💻 Алгоритм:
1⃣Построение графа и подготовка к DFS
Создаем список смежности adjList, где adjList[b] содержит все курсы, зависящие от b.
Каждый курс помечаем цветом:
WHITE = 1 — не посещён
GRAY = 2 — в процессе обработки
BLACK = 3 — полностью обработан
2⃣Обход в глубину (DFS) и детектирование цикла
Для каждого непосещённого узла запускаем dfs.
Если во время обхода обнаруживаем цикл (возврат к GRAY узлу), значит, пройти курсы невозможно.
3⃣Формирование ответа
После завершения DFS по всем узлам формируем порядок курсов из стека (или массива) topologicalOrder, инвертируя его.
😎Решение:
cppКопироватьРедактироватьclass Solution {
public:
int WHITE = 1;
int GRAY = 2;
int BLACK = 3;
vector findOrder(int numCourses, vector& prerequisites) {
bool isPossible = true;
map color;
map adjList;
vector topologicalOrder;
for (int i = 0; i < numCourses; i++) color[i] = WHITE;
for (vector relation : prerequisites) {
int dest = relation[0];
int src = relation[1];
adjList[src].push_back(dest);
}
for (int i = 0; i < numCourses && isPossible; i++) {
if (color[i] == WHITE) {
dfs(i, color, adjList, isPossible, topologicalOrder);
}
}
vector order;
if (isPossible) {
order.resize(numCourses);
for (int i = 0; i < numCourses; i++) {
order[i] = topologicalOrder[numCourses - i - 1];
}
}
return order;
}
void dfs(int node, map& color, map& adjList,
bool& isPossible, vector& topologicalOrder) {
if (!isPossible) return;
color[node] = GRAY;
for (int neighbor : adjList[node]) {
if (color[neighbor] == WHITE) {
dfs(neighbor, color, adjList, isPossible, topologicalOrder);
} else if (color[neighbor] == GRAY) {
isPossible = false;
}
}
color[node] = BLACK;
topologicalOrder.push_back(node);
}
};
Ставь 👍 и забирай 📚 Базу знаний
