一、树的深度：   树中各个节点的深度是一种自顶向下的统计信息。起初，我们已知根节点的深度为0。若节点x的深度为d（x），则它的子节点y的深度就是d（y）=d（x）+1。在深度优先遍历的过程中结合自顶向下的递推，就可以求出每个节点的深度d。 void dfs(int x) { v[x]=1; for(int i=head[x];i;i=nt[x]) { int y=ver[i]; if(v[y]) continue; d[y]=d[x]+1; dfs(y); } }  二、树的重心：   也有许多信息是自底向上进行统计的，比如以每个节点x为根的子树大小size（x）。对于叶子节点，我们已知以它...

一、基本概念：   给定一棵有根树，若节点z既是节点x的祖先，也是节点y的祖先，则称z是x，y的公共祖先。在x，y的所有公共祖先中，深度最大的一个称为x，y的最近公共祖先，记为LCA（x，y）。   LCA（x，y）是x到根的路径与y到根的路径的交汇点。它也是x与y之间的路径上深度最小的节点。求最近公共祖先的方法通常有五种。   在此介绍三种，另外两种还没学。 二、向上标记法：   从x向上走到根节点，并标记所有经过的节点。   从y向上走到根节点，当第一次遇到已标记的节点时，就找到了LCA（x，y）。   对于每个询问，向上标记法的时间复杂度最坏为O（n）。 三、树上倍增法：   树上倍增法...

一、欧拉图：   无向图连通性的小问题——欧拉路问题，俗称一笔画问题。   给定一张无向图，若存在一条从节点S到节点T的路径，恰好不重不漏的经过每条边一次（可以重复经过图中的顶点），则称该路径为S到T的欧拉路。   特别的，若存在一条从节点S出发的路径，敲好不重不漏的经过每条边一次（可以重复经过图中的节点），最终回到起点S，则称该路径为欧拉回路。存在欧拉回路的无向图被称为欧拉图。   欧拉图的判定：   一张无向图为欧拉图，当且仅当无向图连通，并且每个点的度数都是偶数。   欧拉路的存在性判定：   一张无向图中存在欧拉回路，当且仅当无向图连通，并且图中恰好有两个节点的度数为奇数，其他节点的度...

一、A * ：   估价函数的设计准则：估值f（state）≤未来实际代价g（state）。   A * 算法的实现，A * =优先队列BFS+估价函数。   1。优先队列BFS算法维护了一个优先队列，不断从堆中取出当前代价最小的状态 进行扩展。每个状态第一次从堆中取出时，就得到了从初态到该状态的最小代价。   如果给定一个目标状态，需要求出从初态到目标状态的最小代价，那么优先队列 BFS这个优先策略是不完善的。   2。为了提高搜索效率，我们很自然的想到，可以对未来可能产生的代价进行预估。 详细的讲：我们设计一个估价函数，以任意状态为输入，计算出从该状态到目标状态所 需代价的估计值。在搜索中...

一、树状数组的基本应用：   其基本用途是维护前缀和。对于给定的序列a，我们建立一个数组c， c（x）保存序列a的区间     [   x   −   l   o   w   b   i   t   （   x   ）   +   1   ，   x   ]    [x-lowbit（x）+1，x]   [x−lowbit（x）+1，x]中所有数的前缀和。      事实上，数组c可以看作一个树形结构。叶子节点为a[1–N]。   （1）每个内部节点c（x）保存以它为根的子树中所有叶节点的和。   （2）每个内部节点c（x）的子节点个数等于lowbit（x）的位数。   （3）除树根外，每个内...

一、无向图的割点与桥的基本概念：     给定无向连通图G = (V, E) 割点： 对于x∈V，从图中删去节点x以及所有与x关联的边之后，G分裂为两个或两个以上不相连的子图，则称x为割点 割边（桥）： 若对于e∈E，从图中删去边e之后，G分裂成两个不相连的子图，则称e为G的桥或割边 一般无向图（不一定连通）的割点与桥就是它的各个连通块的各点和桥 Tarjan算法基于无向图的深度优先遍历。 时间戳 在图的深度优先遍历过程中，按照每个节点第一次被访问的时间顺序，依次给予N个节点1~N的整数标记，该标记被称为“时间戳”，记为dfn[x] 搜索树 在无向连通图中任选一个节点出发进行深度优先遍历吗，每...

一、基本概念： 流图：   给定一个有向图G= （V，E），若存在r∈V满足，满足从r出发能够到达V中所有的点，则称G是一个流图，记为（G，r），其中r是流图的源点。 流图的搜索树：   在一个流图（G,r）上从r出发，进行深度优先遍历（DFS），每个点只访问一次。所有发生递归的变（x,y）（换言之，从x到y是对y的第一次访问）构成的一棵以r为根的树我们把它称为流图（G,r）的搜索树。 时间戳：   同时，我们在深度优先遍历的过程中按照每个节点第一次被访问的时间顺序，依次给予流图中每个点1~n的标记，该点的标记被称作时间戳，用dfn[x]表示。 边的分类： 对于流图中的有向边（x，y），必是以...

一、二分图的判定：    如果一张图的N个节点可以分成A，B两个非空集合，其中A∩B＝空集，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。A，B分别称为二分图的左部和右部。    定理： 一张无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。        根据该定理，我们可以用染色法进行二分图的判定。大致思想为：尝试用黑白两种颜色标记图中的节点，当一个节点被标记后，它的所有相邻节点应该被标记与它相反的颜色。若标记过程中有冲突，则说明图中存在奇环。二分图染色一般基于深度优先遍历实现，时间复杂度为O（N±M）。    hihoCoder1121 二分图的判定： #i...

一、二分图最小点覆盖：    给定一张二分图，求出一个最小的点集S，使得图中任意一条边都有至少一个端点属于S。这个问题被称为二分图的最小点覆盖，简称最小覆盖。 Konig定理：    二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。        证明：    首先，因为最大匹配是原二分图边集的一个子集，并且所有的边都不相交，所以至少需要从每条匹配边中选出一个端点。因此，最小点覆盖包含的点数不可能小于最大匹配包含的边数。如果能对任意二分图构造出一组点覆盖，其包含的点数等于最大匹配包含的边数，那么定理就能得证。构造方法如下： （1）求出二分图的最大匹配。 （2）从左部每个非匹配点出发，再...

一、简介：    网络流是图论中一个博大精深的分支。若要详细的学习网络流的各种模型与应用，需要不少时间。本篇文章的学习希望我自己可以建立对网络流的初步认识，内容比较浅显，少部分算法和证明的细节会被省略。            一个网络G=（V , E）是一张有向图，图中每条有向边（x，y）∈E都有一个给定的权值c（x，y），称为边的容量。特别的，若（x，y）不属于E，则c（x，y）=0。图中还有两个指定的特殊节点S∈V和T∈V（S≠T），分别称为源点和汇点。        设f（x，y）是定义在节点二元组（x∈V，y∈V）上的实数函数，且满足    （1） f（x，y） ≤ c（x，y）   ...

一、基本概念：    Trie（字典树）是一种用于实现字符串快速检索的多叉树结构。Tire的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符c，就沿着当前节点的c字符指针，走向该指针指向的节点。    初始化：    一棵空Trie仅包含一个根节点，该点的字符指针均指向空。    插入：    当需要插入一个字符串S时，我们令一个指针p起初指向根节点。然后，依次扫描S中的每个字符c：    （1）若P的c字符指针指向一个已经存在的节点Q，则令P=Q。    （2）若P的c字符指针指向空，则新建一个节点Q，令P的c字符指针指向Q，然后令P=Q。    当S中的字符扫描完毕时，在...

一、KMP： 时间复杂度O（N+M）。 next数组求法： （1）初始化next（1）= j = 0，假设next（1----i-1）已经求出，下面求解next（i）。 （2）不断尝试扩展匹配长度j，如果扩展失败（下一个字符不相等），令 j 变为next（j），直至 j 为0（应该开始从头开始匹配）。 （3）如果能够扩展成，匹配长度 j 就增加1。next（i）的值就是 j。 f 数组与next数组的求解过程基本一致。 //A是否为B的子串 //获取A的next数组 //A与B进行匹配，求解 f 数组 nt[1]=0; for(int i=2,j=0;i<=n;i++) { while(...

一、最小表示法：    给定一个字符串S（1----N），如果我们不断把它的最后一个字符放到开头，最终会得到n个字符串，称这n个字符串是循环同构的。这些字符串中字典序最小的一个，称为字符串S的最小表示。    最小表示法求解：    （1）我们先把S复制一份接到它的结尾，得到的字符串记为SS。    （2）初始化 i = 1，j = 2。    （3）通过直接向后扫描的方法，比较b（i）与b（j）两个循环同构串。       如果扫描了n个字符后仍然相等，说明S只由1种字符构成，任意b（i）都是它的最小表示。       如果在 i+k 与 j+k 处发现不相等：       （1）若SS（i...

一、基本概念：    **问题定义：**给定两个字符串 S 和 T（长度分别为 n 和 m），下标从 0 开始， 定义extend[i]等于S[i]…S[n-1]与 T 的最长相同前缀的长度，求出所有的extend[i]。    来看下next[i]与extend[i]的定义：    next[i]： T[i]…T[m - 1]与 T 的最长相同前缀长度；    extend[i]： S[i]…S[n - 1]与 T 的最长相同前缀长度。    求解next[i]的过程就是 T 自己和自己的一个匹配过程。 #include <iostream> #include <strin...