Leetcode 207. Course Schedule

Mingyu Jeon·2020년 5월 25일
0
post-thumbnail

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj_list = defaultdict(list)
        indegree = {}
        for dest, src in prerequisites:
            adj_list[src].append(dest)
            indegree[dest] = indegree.get(dest, 0) + 1

        q = [i for i in range(numCourses) if i not in indegree]

        res = []
        
        while q:
            v = q.pop(0)
            res.append(v)
            if v in adj_list:
                for neighbor in adj_list[v]:
                    indegree[neighbor] -= 1

                    if indegree[neighbor] == 0:
                        q.append(neighbor)

        return True if len(res) == numCourses else False
                
            

https://leetcode.com/problems/course-schedule/

0개의 댓글