C++:

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_multiset<int>> edges(numCourses);
        vector<int> d(numCourses, 0);

        for (int i=0; i<prerequisites.size();i++){
            edges[prerequisites[i].second].insert(prerequisites[i].first);
            d[prerequisites[i].first]++;        
        }
        queue<int> Q;
        int node = 0;

        for (int i=0; i<numCourses; i++){
            if (d[i] ==0 )
                Q.push(i); 
        }
        while(Q.empty() == false){
            int i = Q.front();
            Q.pop();
            node++;

            for (auto iter = edges[i].begin(); iter != edges[i].end(); iter++){
                d[*iter]--;
                if (d[*iter] == 0)
                    Q.push(*iter);
            }  
        }
        return node == numCourses;
    }
};

Python:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if len(prerequisites) == 0:
            return True

        Indegree = collections.defaultdict(int)
        Dict = collections.defaultdict(list)

        for ele in prerequisites:
            Dict[ele[1]].append(ele[0])
            Indegree[ele[0]] += 1

        Q = collections.deque([])

        for i in range(numCourses):
            if Indegree[i] == 0:
                Q.append(i)
                del Indegree[i]

        if len(Q) == 0:
            return False

        while Q:
            parent = Q.popleft()

            for child in Dict[parent]:
                Indegree[child] -= 1
                if Indegree[child] == 0:
                    del Indegree[child]
                    Q.append(child)

        if len(Indegree) > 0:
            return False
        else:
            return True

作者：徐辰潇
链接：https://www.acwing.com/solution/LeetCode/content/10623/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。