# 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?

``````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) {
vector<int> indegree(numCourses);
for (int i = 0; i < numCourses; i++)
indegree[i] = 0;
for (auto pq : prerequisites) {
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;
}
}
``````