祝馀宫

前言：号 · 未授勋之花本文更新于 【算法介绍】连通分量 | 祝馀宫 基础之上。如要阅读下面的内容，建议优先观看上文。本篇内容主要用更加通俗易懂的方式去表现出强连通分量的这个概念以及用 Tarjan 求强连通分量的思想。不会特别注重于讲解基础内容。 序章：武 · 赤角石溃杵首先，我们回顾一下 Tarjan 算法的主要思想。Tarjan 算法的主要思想，是基于每一个点的 Dfs 序，以及对应的一些性质，去判断某一些边，某一些点，他们所代表的内容。 那么所谓强连通分量，就是指有向图中，如果两个点可以互相到达，那么称他们是强连通的，他们就是在同一个强连通分量。对于强连通分量在有向图中，最直观的结构，就是环。 首章：花 · 华馆梦醒形首先我们现在给出一个设定，点的颜色：黑白灰。我们定义一个未走的点是白色，走了但是没有回溯回来的是灰色，完全走完的是黑色。那么我们可以有新的定义表示有向图中的四种边。 树边：显然的是当前的点指向了一个白色的点。 返祖边：我们当前的点指向了灰色的点。 前向边：当前的点指向黑色的点。 横插边：当前的点指向黑色的点。 具体的我们可以看下面的这张图来理解： 我们的深 ...

算法简介：晶片也是一种宝石这篇文章主要讲的是最短路径算法，从最低级的 Floyd 开始，到支持最长路的 Dijskra 的初级代码及其优化，还有支持负边权的 Bellman-Ford 算法。最短路径问题作为图论中解决大多数问题的基础，可以与很多图论模型混搭，是一个泛用型很强的问题类型。 算法演示：不能少了冲天转转例一：改良型平衡稳定器首先，作为多个最短路算法的始祖（可能吧，毕竟这个是基础）一些关于最短路的基础概念都是由 Floyd 算法引导出来的，所以我们首先来讲的算法，就是 Floyd 算法。 首先，我们给定一张图。不管他是无向图还是有向图，我们都可以求最短路。而计算出来的最短路，分为两种： 求出一个点到所有点之间的最短路 —— 单源最短路 求出所有点到所有点之间的最短路 —— 全源最短路 那么我们要用的 Floyd 算法，就是求全源最短路的一个最短路算法。试想一下，如果要求我们在 $O(n^3)$ 的时间复杂度内，实现全源最短路，我们会怎么做？不难想到，就是动态规划。 如果我们设置一个状态 $dp[u][v]$ 表示点 $u$ 到 $v$ 的最短路，那么怎么去求最短路呢？ 不难 ...

算法简介：割舍怜悯之心最小生成树，就是一张图一直删边，直到删成一颗树为止，这叫做生成树，如果这个生成树的边权之和是所有生成树中最小的，那么他被称为最小生成树，前面我们讲过了一个叫做 Boruvka 的算法，虽然他确实是求最小生成树的方法之一，但是他过于远古，不太常用，代码也不如 kruskal 简单，所以说，我们这里将介绍两种新的最小生成树算法，请看副标题 —— Prim & kruskal 。 算法演示：割舍侥幸之心那么最小生成树，生成树生成树，总归就是树，有两种组成部分，一是点，二是边，而 Prim 和 kruskal 算法分别就是代表了基于点的贪心和基于边的贪心，我们来一个逐个击破。 点贪心：割舍痛苦之心首先就是 Prim 算法，他之所以被称为点贪心，是因为这样一个思路： 生成树，必须要把一个图的所有点连起来，变成一个树，也就是说，所有点，我们都将出现在最终的点集合里。所以，我们一开始随便选择一个点，加入最小生成树点集合，然后每次去寻找和我们最小生成树点集合最近的一个点，这样就可以保证每次选出来的边是最短的，然后就一直循环往复，直到所有点都选完。 然后，我们就发现，这样的 ...

算法简介：悬星尽散击云碎一般来讲，我们在大值域的权值线段树问题的时候，都会考虑把它变成离线的，然后进行线段树操作。但是，以万恶的出题人视角，一定会把这唯一的路给断掉，也就是强制在线的大值域权值线段树问题，那么我们就要考虑到动态开点权值线段树了。至于动态开点线段树的应用……想必都知道了吧 —— 线段树合并。 算法演示：璇玑合璧镇昆仑第一部分：星罗宿列天权临那么既然要讲的是动态开点权值线段树的应用，自然要讲动态开点权值线段树。那么我们首先来想，动态开点权值线段树的内存理论应该是多少。首先我们想权值线段树的内存，就和普通线段树一样，都是开了 $4N$ 的，那么如果是动态开点，显而易见我们就可以达到线段树的理论内存，$N\log V$ 其中，$N$ 是数据范围，$V$ 是值域。 有人可能想不通：我们都不知道数据里面最大的那个数，怎么开始数组，怎么建树，怎么往下递归寻找答案？ 上面这个有人是谁，我也不知道，但是有没有一种可能，我们是动态开点，我们不需要建树，我们的内存就是 $N\log V$ ，内存直接开到这么大就够了，也就是一般来讲的 N<<5 。这个 $5$ 的出处是 $2^ ...

算法简介：巡护深林KMP 算法，虽然我们已经在 【算法介绍】字符串算法 | 祝馀宫 中提及，但是现在有了更深的理解，我们这篇文章单独讲 KMP 算法以及其原理。为了凑字数，我们再讲一遍废话。 KMP 算法，全称 $Knuth-Morris-Pratt$ 算法，通过一种特殊的性质匹配两个字符串，从而达到减少匹配次数的算法。 算法演示：漫行山薮变量定义：夏堇芳菲我们对于接下来的一些内容做出如下定义： 名称 定义 子串 不用多说了罢，在字符串中截取任意一段连续的内容，被称为子串下文用 $s[l\dots r]$ 表示字符串 $s$ 的从 $l$ 到 $r$ 的这部分子串。 下文所有关于字符串的计算都是以 1 为开始的下标* 子序列 不要求连续，但是在原字符串中内容顺序相同的字符串。 前缀子串 一个字符串的前缀组成的子串，表示为 $pre(s,i)=s[1\dots i]$ ，即 $s$ 字符串长度为 $i$ 的前缀 后缀子串 一个字符串的后缀组成的子串，表示为 $suf(s, i) = s[n-i+1\dots n]$ ，即 $s$ 字符串长度为 $i$ 的后缀 ...