拓扑排序

有向边 $u\to v$ 表示 $u$ 必须先于 $v$ 完成。拓扑序是一个包含全部顶点的排列，使每条边的起点都出现在终点之前。一个有向图存在拓扑序，当且仅当它没有有向环。

例如边 $0\to2$、$1\to2$ 允许顺序 0, 1, 2 或 1, 0, 2。再加入 $2\to0$ 后产生环，不再存在合法顺序。

入度法

入度为零的顶点没有尚未完成的前置依赖，可以先输出。删除它的出边后，新的零入度顶点也可以输出。若队列为空时仍有顶点未输出，剩余部分就含有环。

from collections import deque

def topological_kahn(adj):
    n = len(adj)
    indegree = [0] * n
    for neighbors in adj:
        for v in neighbors:
            indegree[v] += 1
    queue = deque(u for u in range(n) if indegree[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else None

队列决定在多个合法候选中先选择谁。若要求字典序最小的拓扑序，可以用最小堆替代队列。

DFS 法

DFS 完成顶点 $u$ 时，它沿出边能够访问的后继已经完成。将顶点按完成顺序记录，再反转，就使 $u$ 排在这些后继之前。

检测环需要区分“正在访问”和“已经完成”：边指向递归栈中的顶点说明形成有向环；指向已经完成的顶点则不一定有环。

def topological_dfs(adj):
    state = [0] * len(adj)  # 0 未访问，1 在递归栈中，2 已完成
    order = []

    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                return False
            if state[v] == 0 and not visit(v):
                return False
        state[u] = 2
        order.append(u)
        return True

    for u in range(len(adj)):
        if state[u] == 0 and not visit(u):
            return None
    order.reverse()
    return order

记录完成顺序的列表只需反转一次；如果用栈记录完成顶点，直接逐个弹出就已经是拓扑序，不应再反转。递归实现需注意深链的栈深限制。

两种方法使用邻接表时均为 $O(n+m)$ 时间、$O(n)$ 辅助空间，都能处理非连通有向图并检测环。

例题

• 洛谷 P1113 杂务