目錄

題目：

示例：

分析：

代碼：

---

題目：

示例：

分析：

今天是課程表系列題目的最后一題，因為我在題庫里找不到課程表5了，所以今天的每日一題就是最后一個課程表了。

題目照例是給我們一堆課程的先修關系，然后問我們某課程是否是另一個課程的先修課程，或者是先修課程的先修課程。

如下圖，B，C，D都是A的先修課程。

把問題換個問法，也就是在有向圖中，一個節(jié)點能否走到另一個節(jié)點。

那我們只需要遞歸的去尋找目標課程的先修課程，直到找到對應的先修課程或者是把所有先修課程都找遍了也沒找到。

DFS和BFS都可以，我個人喜歡DFS，所以下面代碼是DFS的。

代碼：

class Solution {
public:unordered_map<int,vector<int>>m;bool find(int n,int cur,int target,unordered_set<int>& s){if(s.count(cur)) return false;  //防止重復遞歸同一個課程s.insert(cur);for(int& i:m[cur]){         //遍歷當前課程的先修課程if(i==target) return true;  //如果等于了目標課程那么返回tureif(find(n,i,target,s)) return true; //再去尋找先修課程的先修課程}return false;}vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {for(auto& p:prerequisites){ //構建有向圖if(m.find(p[0])==m.end()) m[p[0]]=vector<int>(0);m[p[0]].push_back(p[1]);}vector<bool>res;for(auto& q:queries){   //遍歷問題unordered_set<int>s;if(find(numCourses,q[0],q[1],s)) res.push_back(true);else res.push_back(false);}return res;}
};