力扣 207. 课程表

思路

把课程看作图中的节点，所有所需学习的课程构成有向图，问题转化为查看图是否是有向无环图。

拓扑排序: 对有向无环图的顶点进行排序，使得每一条有向边均有边起点定点在有向边终点之前。

bfs

import collections
def canFinish(numCourses, prerequisites):
    # 入度表和邻接表
    indeg, adj = [0 for _ in range(numCourses)], [[] for _ in range(numCourses)]
    # 构建入度表和有向图邻接表
    for e, s in prerequisites:
        indeg[e] += 1
        adj[s].append(e)
    # 查找入度为0的节点
    queue = collections.deque()
    for i in range(len(indeg)):
        if indeg[i] == 0:
            queue.append(i)
    # bfs
    while queue:
        s = queue.popleft()
        numCourses -= 1
        for i in adj[s]:
            indeg[i] -= 1
            if indeg[i] == 0:
                queue.append(i)
    return numCourses == 0

dfs

import collections
def canFinish(numCourses, prerequisites):
    # 邻接表
    adj = [[] for _ in range(numCourses)]
    # 构建有向图邻接表
    for e, s in prerequisites:
        adj[s].append(e)
    flags = [0 for _ in range(numCourses)]

    # dfs
    def dfs(i, flags, adj):
        if flags[i] == -1: return True
        if flags[i] == 1: return False
        flags[i] = 1
        for j in adj[i]:
            if not dfs(j, flags, adj): return False
        flags[i] = -1
        return True
    
    for i in range(numCourses):
        if not dfs(i, flags, adj): return False
    return True