Задача: 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<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        bool isPossible = true;
        map<int, int> color;
        map<int, vector<int>> adjList;
        vector<int> topologicalOrder;

        for (int i = 0; i < numCourses; i++) color[i] = WHITE;

        for (vector<int> 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<int> 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<int, int>& color, map<int, vector<int>>& adjList,
             bool& isPossible, vector<int>& 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);
    }
};

Ставь 👍 и забирай 📚 Базу знаний