字典序最小拓扑排序 - Python 代码实现

字典序最小拓扑排序 - Python 代码实现

题目描述： 给你一个有向无环图（DAG），求它的字典序最小的拓扑排序序列。

输入格式： 第一行输入两个整数 n, m, 表示图中点的数量和边的数量

接下来 m 行每行两个整数 a, b 表示一条边从 a 走向 b //n<=1000, m<=10000

解题思路： 首先，我们需要构建有向图的邻接表表示。

然后，我们使用深度优先搜索（DFS）来进行拓扑排序。从任意一个点开始，遍历它的所有邻接点，先将当前点标记为已访问，然后递归地对邻接点进行 DFS。当 DFS 结束时，将当前点加入结果列表中。由于 DFS 的递归性质，最先访问到的点会最后加入结果列表中，所以最后需要对结果列表进行反转。

最后，输出结果列表即为字典序最小的拓扑排序序列。

代码实现如下：

def dfs(graph, visited, result, node):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, visited, result, neighbor)
    result.append(node)

def topological_sort(n, m, edges):
    # 构建邻接表
    graph = [[] for _ in range(n+1)]
    for a, b in edges:
        graph[a].append(b)
    
    visited = [False] * (n+1)
    result = []
    
    # 从每个点开始进行 DFS
    for i in range(1, n+1):
        if not visited[i]:
            dfs(graph, visited, result, i)
    
    result.reverse()
    return result

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

result = topological_sort(n, m, edges)
for node in result:
    print(node, end=' ')

时间复杂度分析： 构建邻接表的时间复杂度为 O(m)，DFS 的时间复杂度为 O(n+m)，所以总的时间复杂度为 O(n+m)。空间复杂度为 O(n+m)。