解題思路：

這是一個判斷是否是有向無環(huán)圖的題，也是拓?fù)渑判蝾}，網(wǎng)上的解決方案大多是從圖的角度來解釋的，比較復(fù)雜，下面先不管圖論的內(nèi)容，直接就深度優(yōu)先搜索的方法來思考。

首先是建立一個graph，有多少門課程，graph就有多少行，每一行的列數(shù)是不確定的，第i行存儲的是完成課程i所需提前修讀的課程編號。

程序的大循環(huán)是遍歷所有課程，對每一個課程，判斷完成該課程會不會出現(xiàn)沖突，如果出現(xiàn)沖突，就返回false。

在具體判斷第i門課程時，使用深度優(yōu)先搜索，遞歸判斷依賴課程會不會出現(xiàn)環(huán)。通過使用visit數(shù)組，visit[i]=0表示課程i未被訪問，-1表示課程i是待驗證的課程，1表示完成課程i不會出現(xiàn)環(huán)（即可順利修讀課程i）。

?

class Solution { public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//首先建立一個graphvector<vector<int> > graph(numCourses, vector<int>());//graph的第i行存儲的是完成課程i所需提前修讀的課程for(auto num: prerequisites){graph[num[1]].push_back(num[0]);}vector<int> visit(numCourses);//遍歷所有課程，判斷修讀課程i是否會出現(xiàn)沖突for(int i = 0; i < numCourses; i++){if(!dfs(graph, visit, i)) return false;}return true;}bool dfs(vector<vector<int> >& g, vector<int>& visit, int i){if(visit[i] == -1) return false;if(visit[i] == 1) return true;visit[i] = -1; //表示課程i是待選修的，不能在后面的遞歸中出現(xiàn)課程i為需提前修讀的課程for(auto a: g[i]){if(!dfs(g, visit, a)) return false;}visit[i] = 1; //表示課程i能夠成功修讀return true;} };

?

?

?

總結(jié)

以上是生活随笔為你收集整理的Leetcode 207. 课程表 解题思路及C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。