207. Course Schedule

class Solution { public: void mapRepresentations(int numCourses, const vector<pair<int, int> > & edges, map<int, vector<int> > & inLists, map<int, vector<int> > & outLists){ // precondition: both the maps are empty in the beginning // initialize empty lists for all the keys for (int key = 0; key < numCourses; key++){ inLists[key] = {}; outLists[key] = {}; } for (auto & edge: edges){ outLists[edge.first].push_back(edge.second); // outLists: from the Key vertex to one of Value vertices inLists[edge.second].push_back(edge.first); // inLists: from one of the Value vertices to the Key Vertex } } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { map<int, vector<int> > inLists, outLists; mapRepresentations(numCourses, prerequisites, inLists, outLists); // populate the maps queue<int> q; // the outer loop. Store nodes indegree == 0 int counter = 0; for (const auto &entry: inLists) { if (entry.second.empty()) q.push(entry.first); } if (q.empty()) return false; // there is a cycle already! while (!q.empty()) { int curr = q.front(); // take one node from the queue q.pop(); counter++; // remove curr from the graph = update inLists for every one of its neighbors for (const auto & neighbor : outLists[curr]){ // remove indegrees auto iter = find(inLists[neighbor].begin(), inLists[neighbor].end(), curr); inLists[neighbor].erase(iter); // check if push to queue if (inLists[neighbor].empty()){ q.push(neighbor); } } } if (counter != numCourses) return false; else return true; } };