C++ using indegree

  • 0

    the idea is that if we can finish all courses, we can always find a node in graph with indegree being zero. (If we take one certain course, just delete it from our graph)

    class Solution {
    	map<int, multiset<int>> targets;
    	vector<int> indegree;
    	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    		if (prerequisites.empty())
    			return true;
    		indegree.assign(numCourses, 0);
    		for (const auto&pre : prerequisites)
    		for (const auto&t : targets)
    			for (const auto&e : t.second)
    		vector<int>::iterator it;
    		while ((it = std::find(begin(indegree), end(indegree), 0)) != end(indegree))
    			int dis = std::distance(indegree.begin(), it);
    			for (const auto& e: targets[dis])
    			*it = INT_MIN;
    		return (std::find_if(begin(indegree), end(indegree), [&](const int& e)->bool{
    			return e > 0;
    		}) == end(indegree));

Log in to reply

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