一、基本概念 1.定义 拓扑排序是对一个有向无环图（DAG）中所有顶点的一种线性排序，使得对于图中的每一条有向边 (u, v)，顶点 u 在顶点 v 之前。这种排序确保了在执行任务时，所有依赖于某个任务的任务都在该任务完成之后开始。 2.特点 有向无环图：拓扑排序只适用于有向无环图（DAG），因为环会导致依赖关系的循环，使得无法确定顺序。 不唯一性：拓扑排序可能不唯一，同一个图可以有多个有效的拓

一、单调栈简介 单调栈是一种特殊的栈，在普通栈的先进后出基础上满足单调性，从栈顶（栈底）到栈底（栈顶）单调递增或递减。递增的可以称之为单调递增栈，递减的则是单调递减栈。 举个实际的例子（单调递增栈）： 一个序列：3，5，1，9，3，找右侧第一个比当前元素小的元素。 从左往右遍历： 步数 操作 结果（右侧为栈底） 作用 1 遍历到3，此时栈为空，入栈 3 此时右侧还没有比3小的元素

一、引入 最小生成树是一个连接图中所有节点的子图，并使得其边的权重和最小。 本文介绍两种算法，kruskal 算法以及 prim算法 二、Kruskal 1.Kruskal算法简介 Kruskal算法是一种用于求解**加权无向图最小生成树（Minimum Spanning Tree, MST）**的贪心算法。Kruskal算法通过对所有边进行排序并逐步添加到生成树中的方法来构造最小生成树。 2.K

一、Dijkstra（单源最短路） 1.Dijkstra算法简介 迪杰斯特拉算法（Dijkstra’s Algorithm）是一种经典的最短路径算法，用于寻找加权图中从源点到其他各个顶点的最短路径。该算法常用于单源最短路径问题，即已知图中一个起点（源点），计算它到其他所有顶点的最短路径，前提是权重是非负的。 2. 算法思想 迪杰斯特拉算法通过逐步扩展最短路径来构建最终的最短路径树，其基本思想如下：

一、一维前缀和 前缀和是快速获得一个序列的区间和的方法，通过预处理便可以O(1)复杂度获得区间和。 设前缀和数组是sum[i],对于序列a[i]，sum[1] = a[1]; sum[2] = a[1] + a[2]; sum[3] = a[1] + a[2] + a[3];……以此类推 当需要获得[l,r]区间和时，可由sum[r] - sum[l+1] 求出。 12345678910// 预处