简介：本文将介绍拓扑排序的概念，并通过实例展示如何在序列重建问题中运用拓扑排序，解决一些复杂的问题。
拓扑排序是图论中的一个重要概念，它主要用于处理有向无环图（DAG）的节点排序问题。拓扑排序的结果是一个线性序列，满足图中所有的有向边从前面的节点指向后面的节点。这种排序方式在很多实际问题中都有应用，比如任务调度、课程安排等。
在剑指 Offer II 115. 重建序列这道题中，拓扑排序同样是一个有效的解决方法。题目要求根据给定的入度关系，重建一个序列。这种问题可以转化为图论中的拓扑排序问题。具体来说，我们可以将每个元素看作是一个节点，如果元素 A 在元素 B 之前出现，我们就从 A 向 B 画一条有向边。这样，我们就得到了一个有向图。然后，我们可以通过拓扑排序得到一个满足题目要求的序列。
拓扑排序的算法有很多种，其中最常用的是基于深度优先搜索（DFS）的算法。这种算法的基本思想是：从任意一个没有前驱（即入度为0）的节点开始，访问并删除该节点，然后递归地对剩下的图进行同样的操作，直到所有节点都被访问过。这样得到的就是一个拓扑序列。
在实现拓扑排序时，我们需要一个数据结构来存储图的信息。常用的数据结构有邻接表和邻接矩阵。对于稀疏图（即边数较少的图），我们通常使用邻接表；而对于稠密图（即边数较多的图），我们通常使用邻接矩阵。在剑指 Offer II 115. 重建序列这道题中，由于节点的数量较多，而边的数量相对较少，因此我们更适合使用邻接表来存储图的信息。
在具体实现时，我们可以先根据给定的入度关系构建邻接表，并找到所有入度为0的节点作为拓扑排序的起点。然后，我们使用DFS遍历整个图，并在遍历的过程中记录每个节点的访问顺序。最后，我们得到的访问顺序就是一个满足题目要求的序列。
需要注意的是，拓扑排序只能用于有向无环图。如果图中存在环，则无法进行拓扑排序。因此，在进行拓扑排序之前，我们需要先判断图是否是有向无环图。常用的判断方法有深度优先搜索和广度优先搜索等。
总之，拓扑排序是一种非常有用的图论算法，在序列重建等问题中有着广泛的应用。通过掌握拓扑排序的原理和实现方法，我们可以更好地解决一些复杂的问题。