[LeetCode]Course Schedule
Depth First Search.
If there is any backward edge, the answer will be false.
struct mdata {
set<int> *next;
char color;
};
class Solution {
private:
unordered_map<int, struct mdata*> m;
bool DFS_VISIT(int label) {
m[label]->color = 'G';
for(auto i: *(m[label]->next)) {
if(m[i]->color == 'G') {
return false;
}
if(m[i]->color == 'W') {
if(DFS_VISIT(i) == false) {
return false;
}
}
}
m[label]->color = 'B';
return true;
}
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
if(prerequisites.size() == 0) {
return true;
}
for(auto p: prerequisites) {
if(m.find(p.first) == m.end()) {
struct mdata *pm = new struct mdata;
pm->next = new set<int>;
pm->next->insert(p.second);
pm->color = 'W';
m[p.first] = pm;
} else {
m[p.first]->next->insert(p.second);
}
if(m.find(p.second) == m.end()) {
struct mdata *pm = new struct mdata;
pm->next = new set<int>;
pm->color = 'W';
m[p.second] = pm;
}
}
for(auto p: m) {
if(m[p.first]->color == 'W') {
if(DFS_VISIT(p.first) == false) {
return false;
}
}
}
return true;
}
};