210. Course Schedule II

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>> prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        for (auto &e : prerequisites) {
            graph[e[1]].push_back(e[0]);
            ++indegree[e[0]];
        }

        queue<int> q;
        for (int i = 0; i < indegree.size(); ++i) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> answer;
        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (auto &next : graph[curr]) {
                --indegree[next];
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
            --numCourses;
            answer.push_back(curr);
        }

        if (numCourses != 0) {
            return {};
        }
        return answer;
    }
};

Time Complexity

Space Complexity

Miscellane

207. Course Schedule