207. Course Schedule (optimized topological sort)

class Solution { public: void mapRep(int numCourses, vector<pair<int, int>> & prerequisites, unordered_map<int, vector<int>> & ins, unordered_map<int, vector<int>> & outs, queue<int> & zeros){ // a helper function to represent the graph by two maps: // ins is the incoming vertexes to a vertex // outs is the outgoing vertexes // zeros are all the vertexes that have zero incoming edges for (auto & it : prerequisites){ outs[it->first].push_back(it->second); ins[it->second].push_back(it->first); } for (int c : numCourses){ if (ins.find(c) == ins.end()) zeros.push(c); } } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { unordered_map<int, vector<int>> ins; unordered_map<int, vector<int>> outs; queue<int> zeros; mapRep(numCourses, prerequisites, ins, outs, zeros); while(!zeros.empty()){ // remove one element from indegree==0 queue int curr = zeros.front(); zeros.pop(); if (outs.find(curr) == outs.end()) continue; // this vertex has no indegree and no outdegree else { for (int e : outs[curr]){ // for all the out vertex of this vertex auto it = std::find(ins[e].begin(), ins[e].end(), curr); if(it != ins[e].end()) ins[e].erase(it); if(ins[e].empty()) } } } } };