简介 二分图指的是可以把点放到两个集合中，并且集合中不存在边。染色法可以判断一个图是否为二分图，匈牙利算法可以求出二分图最大匹配。匹配指的是二分图中任意两条边都不依赖于同一个顶点的一个子图，简而言之就是在这两边连线不能重复连同一个点，求这些连线的个数。 染色法判定二分图 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。 请你判断这个图是否是二分图。 用 DFS 染色，每个节点和它 ...

简介 最小生成树问题是指用图中所有节点构造一个边权重之和最小的树，可以用 Prim 算法和 Kruskal 算法解决稠密图和稀疏图的最小生成树问题。 Prim 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。 Prim 算法适用于稠密图，与 Dijkstra 算法思想一致，基本思路如下 ...

简介 对于最短距离问题，一共有如下几种算法： Dijkstra 算法是用来计算单源正权最短路算法，它的朴素版适用于稠密图，复杂度 O(n2)O(n^2)O(n2)；堆优化版适合稀疏图，复杂度 O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)。 Bellman-ford 算法用来解决**（有边数限制）的含负权最短路问题**，如果有边数限制一般就只能用此算法求解，复杂度 ...

简介 Hash 的思想就是设计函数 f(A)f(A)f(A) 将某个数据类型映射为整数，由于相同的元素映射后得到的值仍然相同，所以当 f(x)=f(y)f(x)=f(y)f(x)=f(y) 时认为 x=yx=yx=y 即 Hash 的思想。 为了防止哈希碰撞即 f(x)=f(y)f(x)=f(y)f(x)=f(y) 时 x≠yx\ne yx=y，可以多设计几个函数 f1,f2,…f_1,f_2, ...

简介 该数据结构的作用有如下两点： 合并两个集合。 查询两个元素是否在同一个集合中。 基本实现原理是把每个集合用一颗树表示，树根的编号是这个集合的编号，每个节点都存储它的父节点，p[x] 表示 x 的父节点，对于根节点，p[x] = x。 对于优化，可以在查找树根时将路径上的每一个节点的父节点都指向树根。 例题 一共有 nnn 个数，编号是 111 ~ nnn，最开始每个数各自在一个集合中。 ...

Trie 树是用来存储和查找字符串或数字等构成元素不多的数据结构，多用来匹配特定前缀。

KMP 算法通过将相同前缀后缀的长度储存到 next 数组中来避免匹配时重复操作，将平方复杂度的的暴力算法优化到了线性复杂度。

在 C++ 中用数组来模拟单双链表，这样的方式也被称为静态链表，下面以两例题记录 C++ 中的链表应该如何定义和使用。

简介 堆是一种完全二叉树（从上到下，从左到右排列）这意味着它可以被储存到一个数组中，并且对任意一个节点 iii 都有左子节点为 2i2i2i，右子节点为 2i+12i+12i+1，和线段树类似。 当插入元素时，我们需要下滤操作来维持堆的单调性，具体操作流程如下： 将当前节点和两个子节点作比较，如果满足单调性不做任何调整。 如果不满足将较小的子节点与父节点交换，使较小的子节点在上面。 递归执行将放 ...

离散化的目的是将数值大且数量少的一组数据映射为一组较小的数据，比如 [-10^9, 10^9] 范围的数据映射到 [0, 10^5]，从而更方便地用数组储存一些数据。在实战中，通常将这组数据存储到 vector 中之后排序并去重，然后用下标表示某个数字，即将数字映射为下标。