450_拓扑排序面试题¶

from collections import deque

def can_finish(num_courses, prerequisites):
    """
    Kahn 算法：拓扑排序，如果能排出所有节点说明无环
    """
    # 建图：邻接表 + 入度数组
    graph = [[] for _ in range(num_courses)]  # graph[i] = i的后继课程
    in_degree = [0] * num_courses              # 每门课的前置课数量

    for course, prereq in prerequisites:
        graph[prereq].append(course)           # prereq → course
        in_degree[course] += 1                 # course 入度+1

    # 把所有入度为0的课（无前置）加入队列
    queue = deque()
    for i in range(num_courses):
        if in_degree[i] == 0:
            queue.append(i)

    completed = 0                              # 已完成的课程数

    while queue:
        course = queue.popleft()               # 学完这门课
        completed += 1

        for next_course in graph[course]:      # 解锁后继课程
            in_degree[next_course] -= 1        # 后继课程入度-1
            if in_degree[next_course] == 0:    # 前置全部完成，可以学了
                queue.append(next_course)

    return completed == num_courses            # 所有课都能完成说明无环

# 测试
print(can_finish(2, [[1,0]]))           # True（先学0再学1）
print(can_finish(2, [[1,0],[0,1]]))     # False（循环依赖）
print(can_finish(4, [[1,0],[2,0],[3,1],[3,2]]))  # True

def find_order(num_courses, prerequisites):
    """
    在 LeetCode 207 基础上，记录处理顺序
    """
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    order = []                                 # 记录学习顺序

    while queue:
        course = queue.popleft()
        order.append(course)                   # 记录当前课程

        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return order if len(order) == num_courses else []  # 有环返回空

# DFS 版本拓扑排序
def find_order_dfs(num_courses, prerequisites):
    """
    DFS 版本：后序 DFS，最后访问的节点最先完成（逆序就是拓扑序）
    """
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    WHITE, GRAY, BLACK = 0, 1, 2           # 未访问、访问中、已访问
    color = [WHITE] * num_courses
    order = []
    has_cycle = [False]

    def dfs(node):
        if color[node] == GRAY:            # 访问中的节点再次被访问→有环
            has_cycle[0] = True
            return
        if color[node] == BLACK:           # 已处理，跳过
            return

        color[node] = GRAY                 # 标记为访问中
        for neighbor in graph[node]:
            dfs(neighbor)
            if has_cycle[0]:
                return

        color[node] = BLACK                # 标记为已处理
        order.append(node)                 # 后序：处理完所有后继才加入

    for i in range(num_courses):
        if color[i] == WHITE:
            dfs(i)

    if has_cycle[0]:
        return []

    return order[::-1]                     # 逆序就是拓扑序

# 测试
print(find_order(4, [[1,0],[2,0],[3,1],[3,2]]))  # [0,1,2,3] 或 [0,2,1,3]

from collections import defaultdict, deque

def alien_order(words):
    """
    思路：
    1. 比较相邻单词，找出字母顺序关系（边）
    2. 对字母关系图做拓扑排序
    """
    # 初始化所有出现的字母
    adj = defaultdict(set)                 # 邻接表
    in_degree = {c: 0 for word in words for c in word}  # 所有字母的入度

    # 从相邻单词中提取字母顺序
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))

        # 前缀相同但w1更长且w1出现在w2前，非法（如 ["abc", "ab"]）
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""

        for j in range(min_len):
            if w1[j] != w2[j]:            # 找第一个不同的字母
                if w2[j] not in adj[w1[j]]:  # 避免重复边
                    adj[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break                      # 只取第一个不同的位置

    # Kahn 拓扑排序
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    result = []

    while queue:
        c = queue.popleft()
        result.append(c)
        for next_c in adj[c]:
            in_degree[next_c] -= 1
            if in_degree[next_c] == 0:
                queue.append(next_c)

    if len(result) != len(in_degree):      # 有环
        return ""

    return ''.join(result)

# 测试
print(alien_order(["wrt","wrf","er","ett","rftt"]))  # "wertf"
print(alien_order(["z","x"]))                         # "zx"
print(alien_order(["z","x","z"]))                     # ""（有环）

# Kahn 拓扑排序模板
from collections import deque

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u, v in edges:                    # u → v
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # 空列表=有环

# 检测环的简洁方式
has_cycle = (len(topo_order) != n)