from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        in_degree = [0]* numCourses # all courses with its prev courses

        for curr, prev in prerequisites:
            graph[prev].append(curr)
            in_degree[curr] += 1

        curr_course = []
        for i in range(numCourses):
            if in_degree[i] == 0:
                curr_course.append(i)

        while curr_course:
            next_course = []
            for course in curr_course:
                numCourses -= 1
                for nxt in graph[course]:
                    in_degree[nxt] -= 1
                    if in_degree[nxt] == 0:
                        next_course.append(nxt)

            curr_course = next_course

        return False if numCourses else True

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if not prerequisites: # no course
            return True

        return self.bfs(numCourses, prerequisites)


    def bfs(self, num_courses, prerequisites):
        # init
        pre_courses, next_courses = self.get_table(num_courses, prerequisites)
        start_courses = []
        learned_course = []
        for course, pre in pre_courses.items():
            if not pre:
                start_courses.append(course)

        queue = collections.deque(start_courses)
        visited = set()

        while queue:
            course = queue.popleft()
            learned_course.append(course)
            visited.add(course)

            for next_course in next_courses[course]:
                pre_courses[next_course].remove(course)
                if not pre_courses[next_course] and next_course not in visited: # no pre-courses
                    queue.append(next_course)

        else:
            return num_courses == len(learned_course)

    def get_table(self, num_courses, prerequisites):
        pre_courses = {x:[] for x in range(num_courses)} # for record studied
        next_courses = {x:[] for x in range(num_courses)} # for search

        for course in prerequisites:
            pre_courses[course[1]].append(course[0])
            next_courses[course[0]].append(course[1])

        return pre_courses, next_courses