网站站点多少钱,域名时间与网站优化,wordpress更新是乱码,制作公司网站应该考虑什么1--课程表#xff08;207#xff09; 主要思路#xff1a; 用 in 记录每一门课程剩余的先修课程个数#xff0c;当剩余先修课程个数为0时#xff0c;将该课程加入到队列q中。 每修队列q中的课程#xff0c;以该课程作为先修课程的所有课程#xff0c;其剩余先修课程个数…1--课程表207 主要思路 用 in 记录每一门课程剩余的先修课程个数当剩余先修课程个数为0时将该课程加入到队列q中。 每修队列q中的课程以该课程作为先修课程的所有课程其剩余先修课程个数减1 不断将剩余先修课程数为0的课程加入到队列q中当队列为空时若修的课程数等于总课程数则返回true否则返回false #include iostream
#include vector
#include queueclass Solution {
public:bool canFinish(int numCourses, std::vectorstd::vectorint prerequisites) {std::vectorstd::vectorint out; // 存储每一个先修课程对应的课程std::vectorint in; // 存储每一个课程对应的剩余先修课程的个数std::queueint q; // 存储可以修的课程out.resize(numCourses);in.resize(numCourses);// 初始化for(auto pair : prerequisites){int cur pair[0]; // 当前课程int pre pair[1]; // 当前课程的先修课程out[pre].push_back(cur); // 初始化outin[cur];}// 选取可以直接修的课程加入到队列q中for(int i 0; i numCourses; i){if(in[i] 0) q.push(i);}int num 0; // 已经修过的课程数while(!q.empty()){int tmp q.front(); // 修弹出的课程q.pop();num;// 以tmp作为先修课程的课程其剩余的先修课程数减1for(auto course : out[tmp]){in[course] --;if(in[course] 0) q.push(course); // course没有需要先修的课程了因此可以加入到队列q中}}if(num numCourses) return true;else return false;}
};int main(int argc, char* argv[]){// numCourses 2, prerequisites [[1,0],[0,1]]std::vectorstd::vectorint test {{1, 0}, {0, 1}};int numCourses 2;Solution S1;bool res S1.canFinish(numCourses, test);if(res) std::cout true std::endl;else std::cout false std::endl;return 0;
}
2--
