題目描述 [課程表]
現(xiàn)在你總共有 n 門課需要選锈锤，記為 0 到 n-1撵孤。
在選修某些課程之前需要一些先修課程。 例如去枷，想要學(xué)習(xí)課程 0 怖辆，你需要先完成課程 1 是复，我們用一個(gè)匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學(xué)習(xí)竖螃？
示例
輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程淑廊。學(xué)習(xí)課程 1 之前，你需要先完成?課程 0斑鼻；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1猎荠。這是不可能的坚弱。
解題思路
拓?fù)渑判?/p>
- 先構(gòu)建鄰接矩陣（鄰接表更節(jié)約空間 下次再寫把）并且計(jì)算每個(gè)點(diǎn)的入度
- 從所有的點(diǎn)中，選取入度為0的點(diǎn)关摇，放入隊(duì)列
- 出隊(duì)列荒叶，將該點(diǎn)加入拓?fù)渑判虻谋４鏀?shù)組中，并且將以這個(gè)點(diǎn)為頭的邊的尾節(jié)點(diǎn)的入度減1输虱，如果該尾節(jié)點(diǎn)的入度為0則入隊(duì)
- 隊(duì)列為空判斷拓?fù)渑判驍?shù)組的個(gè)數(shù)是否和課程數(shù)相等些楣，不等則有環(huán)
代碼
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size()==0) return true;
vector<int> in(numCourses, 0);
vector<vector<int> > edges(numCourses, vector<int>(numCourses, 0));
for(int i=0;i<prerequisites.size();i++){
edges[prerequisites[i][0]][prerequisites[i][1]] = 1;
in[prerequisites[i][1]] ++;
}
queue<int> q;
vector<int> res;
for(int i=0;i<in.size();i++){
if(in[i]==0) q.push(i);
}
while(!q.empty()){
int i = q.front();
q.pop();
res.push_back(i);
for(int j=0;j<numCourses;j++){
if(edges[i][j]==1){
edges[i][j] = 0;
in[j]--;
if(in[j]==0) q.push(j);
}
}
}
return res.size()==numCourses;
}
};