207. 课程表

[题目链接](207. 课程表 - 力扣（LeetCode）)

解题思路：拓扑排序。有一个可以完成的课程集合set1，有一个需要完成的课程集合set2。每次从set1中拿出一个课程，然后把其影响的节点的入度减减，如果减成了0，则该节点，变成了可以完成的课程，加入set1。依次做下去，如果set2空了，代表全部都完成了，如果set1空了，set2没空，那么就不能完成

代码

class Solution:

    class node:
        def __init__(self, key, pre):
            self.key = key
            self.pre = pre
            self.nexts = set()

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        cources = {}
        need_do = set()
        cando = set()
        for cource in prerequisites:
            # cource[0] 就是不能完成的   cource[1]就是可以先完成的
            if cource[0] not in cources:  # 第一次出现这个课程
                new_cource = self.node(cource[0], 1)
                cources[cource[0]] = new_cource
                need_do.add(cource[0])
            else:
                cources[cource[0]].pre += 1
                if cource[0] in cando:
                    cando.remove(cource[0])
                    need_do.add(cource[0])

            if cource[1] not in cources:
                new_cource = self.node(cource[1], 0)
                new_cource.nexts.add(cource[0])
                cources[cource[1]] = new_cource
                cando.add(cource[1])
            else:
                cources[cource[1]].nexts.add(cource[0])
        while cando:
            if not need_do:
                return True
            cur_cource = cando.pop()
            for next_cource in cources[cur_cource].nexts:
                cources[next_cource].pre -= 1
                if cources[next_cource].pre == 0:
                    cando.add(next_cource)
                    need_do.remove(next_cource)
        return not need_do