Topological sort

拓扑排序，用于排序有向无环图（DAG）或者判断图中是否有环。

使用邻接表存储图，并存储每个 vertex 的 indegree 数。循环结束如果还有 vertex 的 indegree 不为 0，则图中有环。

时间复杂度 $O(V+E)$。空间复杂度 $O(V+E)$。

相关题目

207. Course Schedule

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    adjlist = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for c1, c2 in prerequisites:
        adjlist[c1].append(c2)
        indeg[c2] += 1
    q = deque(x for x in range(numCourses) if indeg[x] == 0)
    nedges = len(prerequisites)
    while q:
        c1 = q.popleft()
        for c2 in adjlist[c1]:
            indeg[c2] -= 1
            if indeg[c2] == 0:
                q.append(c2)
            nedges -= 1
    return nedges == 0

另见

• Topological sorting