問題概要

0からnumCourses-1までの整数で表される複数のコースが存在します。配列prerequisitesの各要素prerequisites[i] = [a_i, b_i]は、コースa_iを受講する前にb_iを完了する必要があることを示します。

すべてのコースを受講可能な順序を返してください。複数の有効な順序が存在する場合は、そのいずれかを返します。不可能な場合は空配列を返します。

例1

入力: numCourses = 2, prerequisites = [[1,0]]
出力: [0,1]

例2

入力: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
出力: [0,2,1,3]

解法アプローチ

• 深さ優先探索(DFS)によるトポロジカルソート
• 幅優先探索(BFS)を用いた Kahn's アルゴリズム

コード実装

DFSによる解法

class DfsSolver {
private:
    std::vector adjacencyList;
    std::vector<int> status;
    std::vector<int> order;
    bool isAcyclic = true;

    void depthFirstSearch(int node) {
        status[node] = 1; // 探索中
        for (int neighbor : adjacencyList[node]) {
            if (status[neighbor] == 0) {
                depthFirstSearch(neighbor);
                if (!isAcyclic) return;
            } else if (status[neighbor] == 1) {
                isAcyclic = false;
                return;
            }
        }
        status[node] = 2; // 完了
        order.push_back(node);
    }

public:
    std::vector<int> solve(int numCourses, std::vector& requirements) {
        adjacencyList.resize(numCourses);
        status.resize(numCourses);
        
        for (const auto& req : requirements) {
            adjacencyList[req[1]].push_back(req[0]);
        }

        for (int i = 0; i < numCourses && isAcyclic; ++i) {
            if (status[i] == 0) {
                depthFirstSearch(i);
            }
        }

        if (!isAcyclic) return {};
        std::reverse(order.begin(), order.end());
        return order;
    }
};

BFSによる解法

class BfsSolver {
private:
    std::vector adjacencyList;
    std::vector<int> indegree;
    std::vector<int> result;

public:
    std::vector<int> solve(int numCourses, std::vector& requirements) {
        adjacencyList.resize(numCourses);
        indegree.resize(numCourses);
        
        for (const auto& req : requirements) {
            adjacencyList[req[1]].push_back(req[0]);
            indegree[req[0]]++;
        }

        std::queue<int> zeroIndegree;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                zeroIndegree.push(i);
            }
        }

        while (!zeroIndegree.empty()) {
            int current = zeroIndegree.front();
            zeroIndegree.pop();
            result.push_back(current);
            
            for (int neighbor : adjacencyList[current]) {
                if (--indegree[neighbor] == 0) {
                    zeroIndegree.push(neighbor);
                }
            }
        }

        return (result.size() == numCourses) ? result : std::vector<int>{};
    }
};