leetcode day 3 【207. 课程表】图拓扑排序

• 图的拓扑序列，求序列长度是否等于顶点数即可。

第一次：两个list分别记录入度顶点和出度顶点

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        inlist = [[] for _ in range(numCourses)]
        outlist = [[] for _ in range(numCourses)]
        for back, front in prerequisites:
            outlist[front].append(back)
            inlist[back].append(front)

        noin = deque()
        for i in range(numCourses):
            if len(inlist[i]) == 0:
                noin.append(i)
        count = 0
        while(noin):
            outcourse = noin.popleft()
            count += 1
            for course in outlist[outcourse]:
                inlist[course].remove(outcourse)
                if len(inlist[course]) == 0:
                    noin.append(course)
        if count != numCourses:
            return False
        else:
            return True

第二次：两个list，一个记录顶点出度点，一个记录顶点入度数（而不是入度的点，因为不需要知道这个细节）

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        outlist = [[] for _ in range(numCourses)]
        indegree = [0]*numCourses
        print(indegree)
        for back, front in prerequisites:
            outlist[front].append(back)
            indegree[back] += 1
        noin = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                noin.append(i)
        count = 0
        while(noin):
            outcourse = noin.popleft()
            count += 1
            for course in outlist[outcourse]:
                indegree[course] -= 1
                if indegree[course] == 0:
                    noin.append(course)
        if count != numCourses:
            return False
        else:
            return True

第三次：简化代码！！！！

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        outlist = [[] for _ in range(numCourses)]
        indeg = [0]*numCourses
        for back, front in prerequisites:
            outlist[front].append(back)
            indeg[back] += 1
        q = deque()
        q.extend([vertex for vertex in range(numCourses) if indeg[vertex]==0])
        count = 0
        while(q):
            outcourse = q.popleft()
            count += 1
            for course in outlist[outcourse]:
                indeg[course] -= 1
                if indeg[course] == 0:
                    q.append(course)
        return count == numCourses

结果

1.python中对list/queue等添加元素时，append( )和extend( ) 的区别：

所以第三次代码中要用extend而不能用append添加，否则会直接添加一个整体列表。

2.若想初始化两个完全相同的变量，不能初始化A后，直接令B=A，这是因为B实际指向A的同一片地址了，所有对B的操作实际上也是对A的操作。应该再初始化一遍B（见第一次尝试）。