# Course Schedule

Question:

http://www.lintcode.com/en/problem/course-schedule/

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Answer:

```
class Solution {
public:
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: true if can finish all courses or false
*/
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
// Write your code here
vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses);
for (int i = 0; i < numCourses; i++)
indegree[i] = 0;
for (auto pq : prerequisites) {
adj[pq.first].push_back(pq.second);
indegree[pq.second]++;
}
stack<int> st;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0)
st.push(i);
}
int count = 0;
while (!st.empty()) {
int v1 = st.top();
st.pop();
count++;
for (auto v2 : adj[v1]) {
indegree[v2]--;
if (indegree[v2] == 0)
st.push(v2);
}
}
return count == numCourses;
}
}
```