題目鏈接：https://leetcode-cn.com/problems/course-schedule/

解題思路

廣度優(yōu)先搜索

建立依賴(lài)關(guān)系圖：[a,b] 表示課程a依賴(lài)于課程b，此時(shí)圖中由b節(jié)點(diǎn)指向a節(jié)點(diǎn)即： b->a；

首先為所有應(yīng)節(jié)點(diǎn)建立鄰接表adjacents，建立計(jì)數(shù)器count統(tǒng)計(jì)節(jié)點(diǎn)中不為入度不為0的個(gè)數(shù)；然后統(tǒng)計(jì)圖中入度為0的節(jié)點(diǎn)，將所有入度為0的節(jié)點(diǎn)加入到隊(duì)列queue中。

當(dāng)隊(duì)列queue不為空時(shí)：
首先獲取隊(duì)列中的首節(jié)點(diǎn)pre，并通過(guò)鄰接表訪問(wèn)與pre相連的節(jié)點(diǎn)，并將相連節(jié)點(diǎn)的入度減1；如果入度減1后，該節(jié)點(diǎn)的入度為0，則將該節(jié)點(diǎn)加入到隊(duì)列中。最后將pre從隊(duì)列中彈出，同時(shí)count減1。

最后，當(dāng)count不為0時(shí)，說(shuō)明存在節(jié)點(diǎn)未加入隊(duì)列，說(shuō)明遍歷所有pre節(jié)點(diǎn)，都無(wú)法將某個(gè)節(jié)點(diǎn)的入度減為0，即該節(jié)點(diǎn)處于環(huán)中，不符題目，返回false；當(dāng)count為0時(shí)，說(shuō)明所有節(jié)點(diǎn)都加入隊(duì)列，并已從隊(duì)列中彈出，返回true。

代碼

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<int> inDegree(numCourses,0);//記錄所有頂點(diǎn)的入度
        vector<vector<int>> adjacents(numCourses); //鄰接表
        queue<int> nodeQ;
        int counts = numCourses;
        for(auto &&node:prerequisites){
            inDegree[node[0]]++;//入頂點(diǎn)
            adjacents[node[1]].push_back(node[0]);//出頂點(diǎn)
        }
        for(int i=0;i<numCourses;i++){
            //入度為0的先入隊(duì)列
            if(inDegree[i] == 0) nodeQ.push(i),counts--;
        }
        while(!nodeQ.empty()){
            int pre = nodeQ.front();
            for(auto&& ajNode:adjacents[pre]){
                inDegree[ajNode]--;
                if(inDegree[ajNode] == 0) 
                    nodeQ.push(ajNode),counts--;
            }
            nodeQ.pop();// pop out
        }
        if(counts != 0) return false;
        return true;
    }
};

結(jié)果

執(zhí)行用時(shí)：8 ms, 在所有 C++ 提交中擊敗了99.80%的用戶
內(nèi)存消耗：12.9 MB, 在所有 C++ 提交中擊敗了85.46%的用戶