Accepted 264ms c++ solution using topological sort and queue.


  • 0

    Accepted 264ms c++ solution using topological sort for Course Schedule.

    class Solution {
    public:
    	bool canFinish(int numCourses, std::vector<std::pair<int, int> > &prerequisites) {
    		std::vector<std::unordered_set<int> > need(numCourses);
    		for (std::size_t i = 0; i != prerequisites.size(); ++i)
    			need[prerequisites[i].second].insert(prerequisites[i].first);
    		std::vector<int> indegree(numCourses);
    		for (int i = 0; i != numCourses; ++i)
    			for(auto it = need[i].begin(); it != need[i].end(); ++it)
    				++indegree[*it];
    		std::queue<int> zeros;
    		for (int i = 0; i != numCourses; ++i)
    			if (indegree[i] == 0)
    				zeros.push(i);
    		while (!zeros.empty()) {
    			int seq = zeros.front();
    			zeros.pop();
    			for (auto it = need[seq].begin(); it != need[seq].end(); ++it)
    				if (--indegree[*it] == 0)
    					zeros.push(*it);
    			--numCourses;
    		}
    		return numCourses == 0;
    	}
    };
    

    Accepted 500ms c++ solution using topological sort for Course Schedule II.

    class Solution {
    public:
    	std::vector<int> findOrder(int numCourses, std::vector<std::pair<int, int> >& prerequisites) {
    		std::vector<std::unordered_set<int> > need(numCourses);
    		for (std::size_t i = 0; i != prerequisites.size(); ++i)
    			need[prerequisites[i].second].insert(prerequisites[i].first);
    		std::vector<int> indegree(numCourses);
    		for (int i = 0; i != numCourses; ++i)
    			for(auto it = need[i].begin(); it != need[i].end(); ++it)
    				++indegree[*it];
    		std::queue<int> zeros;
    		for (int i = 0; i != numCourses; ++i)
    			if (indegree[i] == 0)
    				zeros.push(i);
    		std::vector<int> res;
    		while (!zeros.empty()) {
    			int seq = zeros.front();
    			zeros.pop();
    			res.push_back(seq);
    			for (auto it = need[seq].begin(); it != need[seq].end(); ++it)
    				if (--indegree[*it] == 0)
    					zeros.push(*it);
    		}
    		return res.size() == numCourses ? res : std::vector<int>();
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.