放坡偏序(从拓扑排序开始)

from collections import defaultdict, deque

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    queue = deque([u for u in graph if in_degree[u] == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(result) == len(graph):
        return result
    else:
        raise ValueError("Graph has at least one cycle, topological sort not possible")

# 示例图
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

print(topological_sort(graph))  # 输出: ['A', 'B', 'C', 'E', 'D', 'F']