c++怎么实现拓扑排序

拓扑排序是一种对有向无环图（DAG）进行排序的算法，具体来说就是将其节点按照一定的顺序排列，使得对于任意一条边 i -> j，都有i排在j的前面。拓扑排序可以应用于很多领域，比如编译器优化、任务调度、依赖关系等。

以下是拓扑排序的实现过程：

1. 统计每个节点的入度

遍历图中的每个节点，记录它们的入度，即与它们相连的所有节点的出度之和。这个过程可以利用邻接表来完成，时间复杂度为 O(|V| + |E|)。

2. 检索入度为 0 的节点

在入度统计完成后，我们可以遍历一遍节点数组，找到所有入度为 0 的节点，将它们加入一个队列Q中。

3. 遍历入度为 0 的节点

从队列Q中取出一个入度为 0 的节点，将它输出到排序结果中，并将它的所有出边指向的节点的入度减 1。如果某个节点的入度减为 0，则将它加入队列Q中。

重复上述过程，直到所有节点都被输出到排序结果中。如果队列Q变为空，但还有节点的入度不为 0，则说明图中存在环，该图不是 DAG。

拓扑排序的时间复杂度为 O(|V| + |E|)，其中|V|和|E|分别是图中节点和边的数量。因为对于每个节点我们需要统计一遍入度，遍历所有节点也需要 O(|V|) 的时间，而对于每条边我们至多遍历一次，因此总时间复杂度为 O(|V| + |E|)。

以下是基于邻接表的 Python 代码示例：

from collections import deque

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    queue = deque(node for node in in_degree if in_degree[node] == 0)
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    if len(result) != len(graph):
        raise ValueError("Input graph contains a cycle")
    return result