Simple C++ BFS solution(20+ lines)


  • 0

    I'm learning C++, so my "for" struct is still C style.

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int>> forwTo(numCourses);
            vector<int>	reqNum(numCourses);
            vector<int> order;
            for(int i = 0; i < prerequisites.size(); i++) {
            	pair<int, int> edge = prerequisites[i];
            	reqNum[edge.first] += 1;
            	forwTo[edge.second].push_back(edge.first);
            }
            queue<int> freeCourse;
            for(int i = 0; i < numCourses; i++) 
            	if (reqNum[i] == 0) freeCourse.push(i);
            while(!freeCourse.empty()) {
            	int cur = freeCourse.front();
            	freeCourse.pop();
            	order.push_back(cur);
            	for(int p = 0; p < forwTo[cur].size(); p++) {
            		int toCourse = forwTo[cur][p];
            		reqNum[toCourse] -= 1;
            		if (reqNum[toCourse] == 0) freeCourse.push(toCourse);
            	}
            }
            if (order.size() != numCourses) return vector<int>();
            	else return order;
        }
    };
    

Log in to reply
 

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