LeetCode 1462. 课程安排 IV

LeetCode 1462. 课程安排 IV
idea:BFS+set
data:20201014

#include <vector>
#include <list>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
/*******************/
//LeetCode 1462. 课程安排 IV 
//看了T101402LC例程后我的程序 C++、建图、BFS
/*******************/
class Solution {
    
public:vector<set<int>> WhocldAchThis;//“WhocldAchThis”存储的是对应行——所有可以到达这一点的点，通过后面迭代，不是直接到的也包含其中了vector<vector<int>> IcldAchWho;//“IcldAchWho”存储的是对应行——我可以 直接 到达的点vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
    WhocldAchThis.resize(n);IcldAchWho.resize(n);vector<int> InDegree(n, 0);//初始化为n个0InDegree.resize(n);//统计一下每个点的入度for (int i = 0; i < prerequisites.size(); i++) {
    IcldAchWho[prerequisites[i][0]].push_back(prerequisites[i][1]);InDegree[prerequisites[i][1]]++;}//开始BFS,第一次手动找一个入度为0的点，放进队列里面queue<int> que;for (int i = 0; i < InDegree.size(); i++) {
    //找初始的入度为0的点if (InDegree[i] == 0) {
    que.push(i);}}//根据模板，这里可以开始循环了while (!que.empty()) {
    int CurVal = que.front();que.pop();//对我能到达的所有点都进行遍历,我能到达的点保存在“IcldAchWho[CurVal][i]”中for (int i = 0; i < IcldAchWho[CurVal].size(); i++) {
    //第一部处理，把能到我的都给我的下一个WhocldAchThis[IcldAchWho[CurVal][i]].insert(WhocldAchThis[CurVal].begin(), WhocldAchThis[CurVal].end());//第二部处理，把我自己也给到下一个，我也是能到达下一个的 WhocldAchThis[IcldAchWho[CurVal][i]].insert(CurVal);//当操作完“我”之后，我所指向的人的入度都得减一InDegree[IcldAchWho[CurVal][i]]--;//如果我的入度为零，那也进入队列，等一会处理if (InDegree[IcldAchWho[CurVal][i]] == 0) {
    que.push(IcldAchWho[CurVal][i]);}}}//for (int i = 0; i < WhocldAchThis.size(); i++) {
    // for (set<int>::iterator j = WhocldAchThis[i].begin(); j != WhocldAchThis[i].end();j++) {
    // printf("%d ", *j);// }// printf("%n");//}//目前所有处理都已经完成，可以到达i的点都保存在WhocldAchThis[i]中，此时遍历queries比较就好vector<bool> res;for (int i = 0; i < queries.size(); i++) {
    if (WhocldAchThis[queries[i][1]].find(queries[i][0]) != WhocldAchThis[queries[i][1]].end()) {
    res.push_back(1);}else {
     res.push_back(0); }}return res;}
};int main(void) {
    Solution solution;vector<vector<int>> prere;prere.resize(3);prere[0].push_back(1); prere[0].push_back(2);prere[1].push_back(1); prere[1].push_back(0);prere[2].push_back(2); prere[2].push_back(0);vector<vector<int>> que;que.resize(2);que[0].push_back(0); que[0].push_back(1);que[1].push_back(1); que[1].push_back(2);vector<bool> res;res = solution.checkIfPrerequisite(3, prere, que);return 1;
}