常用算法代码

目录 目录 1 Graph 图论 3 | DAG 的深度优先搜索标记 3 | 无向图找桥 3 | 无向图连通度(割) 3 | 最大团问题 DP + DFS 3 | 欧拉路径 O(E) 3 | DIJKSTRA 数组实现 O（N^2） 3 | DIJKSTRA O(E * LOG E) 4 | BELLMANFORD 单源最短路 O(VE) 4 | SPFA(SHORTEST PATH FASTER ALGORITHM) 4 | 第 K 短路（DIJKSTRA） 5 | 第 K 短路（A*） 5 | PRIM 求 MST 6 | 次小生成树 O(V^2) 6 | 最小生成森林问题(K 颗树)O(MLOGM). 6 | 有向图最小树形图 6 | MINIMAL STEINER TREE 6 | TARJAN 强连通分量 7 | 弦图判断 7 | 弦图的 PERFECT ELIMINATION 点排列 7 | 稳定婚姻问题 O(N^2) 7 | 拓扑排序 8 | 无向图连通分支(DFS/BFS 邻接阵) 8 | 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) 8 | 有向图最小点基(邻接阵)O(N^2) 9 | FLOYD 求最小环 9 | 2-SAT 问题 9 Network 网络流 11 | 二分图匹配（匈牙利算法 DFS 实现） 11 | 二分图匹配（匈牙利算法 BFS 实现） 11 | 二分图匹配（HOPCROFT－CARP 的算法） 11 | 二分图最佳匹配（KUHN MUNKRAS 算法 O(M*M*N)） 11 | 无向图最小割 O(N^3) 12 | 有上下界的最小(最大)流 12 | DINIC 最大流 O(V^2 * E) 12 | HLPP 最大流 O(V^3) 13 | 最小费用流 O(V * E * F) 13 | 最小费用流 O(V^2 * F) 14 | 最佳边割集 15 | 最佳点割集 15 | 最小边割集 15 | 最小点割集（点连通度） 16 | 最小路径覆盖 O(N^3) 16 | 最小点集覆盖 16 Structure 数据结构 17 | 求某天是星期几 17 | 左偏树 合并复杂度 O(LOG N) 17 | 树状数组 17 | 二维树状数组 17 | TRIE 树(K 叉) 17 | TRIE 树(左儿子又兄弟) 18 | 后缀数组 O(N * LOG N) 18 | 后缀数组 O(N) 18 | RMQ 离线算法 O(N*LOGN)+O(1) 19 | RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法 (O(NLOGN + Q)) 19 | RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA 19 | LCA 离线算法 O(E)+O(1) 20 | 带权值的并查集 20 | 快速排序 20 | 2 台机器工作调度 20 | 比较高效的大数 20 | 普通的大数运算 21 | 最长公共递增子序列 O(N^2) 22 | 0-1 分数规划 22 | 最长有序子序列（递增/递减/非递增/非递减） 22 | 最长公共子序列 23 | 最少找硬币问题（贪心策略-深搜实现） 23 | 棋盘分割 23 | 汉诺塔 23 | STL 中的 PRIORITY_QUEUE 24 | 堆栈 24 | 区间最大频率 24 | 取第 K 个元素 25 | 归并排序求逆序数 25 | 逆序数推排列数 25 | 二分查找 25 | 二分查找（大于等于 V 的第一个值） 25 | 所有数位相加 25 Number 数论 26 1 |递推求欧拉函数 PHI(I) 26 |单独求欧拉函数 PHI(X) 26 | GCD 最大公约数 26 | 快速 GCD 26 | 扩展 GCD 26 | 模线性方程 A * X = B (% N) 26 | 模线性方程组 26 | 筛素数 [1..N] 26 | 高效求小范围素数 [1..N] 26 | 随机素数测试(伪素数原理) 26 | 组合数学相关 26 | POLYA 计数 27 | 组合数 C(N, R) 27 | 最大 1 矩阵 27 | 约瑟夫环问题（数学方法） 27 | 约瑟夫环问题（数组模拟） 27 | 取石子游戏 1 27 | 集合划分问题 27 | 大数平方根（字符串数组表示） 28 | 大数取模的二进制方法 28 | 线性方程组 A[][]X[]=B[] 28 | 追赶法解周期性方程 28 | 阶乘最后非零位,复杂度 O(NLOGN) 29 递归方法求解排列组合问题 30 | 类循环排列 30 | 全排列 30 | 不重复排列 30 | 全组合 31 | 不重复组合 31 | 应用 31 模式串匹配问题总结 32 | 字符串 HASH 32 | KMP 匹配算法 O(M+N) 32 | KARP-RABIN 字符串匹配 32 | 基于 KARP-RABIN 的字符块匹配 32 | 函数名: STRSTR 32 | BM 算法的改进的算法 SUNDAY ALGORITHM 32 | 最短公共祖先（两个长字符串） 33 | 最短公共祖先（多个短字符串） 33 Geometry 计算几何 34 | GRAHAM 求凸包 O(N * LOGN) 34 | 判断线段相交 34 | 求多边形重心 34 | 三角形几个重要的点 34 | 平面最近点对 O(N * LOGN) 34 | LIUCTIC 的计算几何库 35 | 求平面上两点之间的距离 35 | (P1-P0)*(P2-P0)的叉积 35 | 确定两条线段是否相交 35 | 判断点 P 是否在线段 L 上 35 | 判断两个点是否相等 35 | 线段相交判断函数 35 | 判断点 Q 是否在多边形内 35 | 计算多边形的面积 35 | 解二次方程 AX^2+BX+C=0 36 | 计算直线的一般式 AX+BY+C=0 36 | 点到直线距离 36 | 直线与圆的交点，已知直线与圆相交 36 | 点是否在射线的正向 36 | 射线与圆的第一个交点 36 | 求点 P1 关于直线 LN 的对称点 P2 36 | 两直线夹角（弧度） 36 ACM/ICPC 竞赛之 STL 37 ACM/ICPC 竞赛之 STL 简介 37 ACM/ICPC 竞赛之 STL--PAIR 37 ACM/ICPC 竞赛之 STL--VECTOR 37 ACM/ICPC 竞赛之 STL--ITERATOR 简介 38 ACM/ICPC 竞赛之 STL--STRING 38 ACM/ICPC 竞赛之 STL--STACK/QUEUE 38 ACM/ICPC 竞赛之 STL--MAP 40 ACM/ICPC 竞赛之 STL--ALGORITHM 40 STL IN ACM 41 头文件 42 线段树 43 求矩形并的面积（线段树+离散化+扫描线） 43 求矩形并的周长（线段树+离散化+扫描线） 44 ### 常用算法代码概览 #### Graph 图论 - **DAG 的深度优先搜索标记**：在有向无环图（DAG）中进行深度优先搜索，并标记已访问节点，常用于寻找可达性、拓扑排序等问题。 - **无向图找桥**：在无向图中找到所有桥（即移除该边将导致图不再连通的边），通常使用 Tarjan 的算法或 DFS 来实现。 - **无向图连通度(割)**：计算无向图的连通度，即移除多少个顶点才能使得图不连通。可以使用多次 DFS 或 BFS 来完成。 - **最大团问题 DP + DFS**：通过动态规划结合深度优先搜索来解决寻找图中最大的完全子图（团）的问题。 - **欧拉路径 O(E)**：寻找图中一条经过每条边恰好一次的路径，适用于具有欧拉路径的图。 - **DIJKSTRA 数组实现 O（N^2）**：Dijkstra 算法的一种实现方式，适用于稠密图或使用邻接矩阵存储的图。 - **DIJKSTRA O(E * LOG E)**：使用优先队列优化 Dijkstra 算法的时间复杂度，适合稀疏图。 - **BELLMANFORD 单源最短路 O(VE)**：适用于含有负权重边的图，能够检测负权回路的存在。 - **SPFA(SHORTEST PATH FASTER ALGORITHM)**：比 Bellman-Ford 算法更快的单源最短路径算法，特别适用于存在大量负权重边的情况。 - **第 K 短路（DIJKSTRA）**：使用 Dijkstra 算法变种寻找第 K 条最短路径。 - **第 K 短路（A*）**：利用启发式搜索算法 A* 来寻找第 K 条最短路径。 - **PRIM 求 MST**：Prim 算法用于求解最小生成树问题。 - **次小生成树 O(V^2)**：寻找次小生成树，即在所有生成树中第二小的那棵。 - **最小生成森林问题(K 颗树)O(MLOGM)**：在包含多个连通分量的图中，为每个连通分量寻找最小生成树。 - **有向图最小树形图**：在有向图中寻找一棵包含所有顶点的树形子图，使得树的所有边都是原图中的边。 - **MINIMAL STEINER TREE**：寻找 Steiner 树问题的最优解。 - **TARJAN 强连通分量**：使用 Tarjan 算法找到图中的所有强连通分量。 - **弦图判断**：判断一个图是否为弦图。 - **弦图的 PERFECT ELIMINATION 点排列**：在弦图中找到一个完美的消除顺序。 - **稳定婚姻问题 O(N^2)**：解决 Gale-Shapley 稳定匹配问题，即在男女双方各自偏好列表下找到稳定的婚姻匹配。 - **拓扑排序**：对于有向无环图，按照某种顺序排列图中的所有顶点，使得对于任意一条有向边(u,v)，都有 u 在 v 之前出现。 - **无向图连通分支(DFS/BFS 邻接阵)**：使用深度优先搜索或广度优先搜索来找出无向图的连通分支。 - **有向图强连通分支(DFS/BFS 邻接阵)O(N^2)**：使用 DFS 或 BFS 找出有向图中的所有强连通分支。 - **有向图最小点基(邻接阵)O(N^2)**：寻找有向图中的最小点基，即最小的顶点集合，移除这些顶点后图将不再连通。 - **FLOYD 求最小环**：使用 Floyd 算法来求解所有顶点间的最短路径，并从中找出最小环。 - **2-SAT 问题**：解决 2-可满足性问题，即是否存在一种变量赋值方案使得所有由变量和它们的否定构成的子句都能被满足。 #### Network 网络流 - **二分图匹配（匈牙利算法 DFS 实现）**：在二分图中寻找最大匹配，使用 DFS 实现匈牙利算法。 - **二分图匹配（匈牙利算法 BFS 实现）**：在二分图中寻找最大匹配，使用 BFS 实现匈牙利算法。 - **二分图匹配（HOPCROFT－CARP 的算法）**：更高效的二分图匹配算法。 - **二分图最佳匹配（KUHN MUNKRAS 算法 O(M*M*N)）**：在二分图中寻找最小成本的最大匹配。 - **无向图最小割 O(N^3)**：寻找无向图中的最小割，即移除哪些边可以使图分为两个部分。 - **有上下界的最小(最大)流**：在流量网络中寻找满足上下界约束条件的最小或最大流。 - **DINIC 最大流 O(V^2 * E)**：Dinic 算法用于求解最大流问题。 - **HLPP 最大流 O(V^3)**：Huang-Lin-Pai-Papadimitriou 算法，一种用于求解最大流问题的方法。 - **最小费用流 O(V * E * F)**：寻找最小费用流，即在有费用的网络中找到总费用最小的流。 - **最小费用流 O(V^2 * F)**：另一种求解最小费用流的方法。 - **最佳边割集**：在图中寻找最佳的边割集。 - **最佳点割集**：在图中寻找最佳的点割集。 - **最小边割集**：在图中寻找最小的边割集。 - **最小点割集（点连通度）**：在图中寻找最小的点割集。 - **最小路径覆盖 O(N^3)**：在有向图中寻找最小路径覆盖。 - **最小点集覆盖**：在图中寻找最小的点集覆盖。 #### Structure 数据结构 - **求某天是星期几**：根据日期计算某一天是星期几。 - **左偏树 合并复杂度 O(LOG N)**：左偏树是一种自平衡二叉搜索树，支持高效合并操作。 - **树状数组**：用于维护数组的前缀和，支持查询和更新操作。 - **二维树状数组**：扩展了树状数组的应用场景，支持二维数组的前缀和查询。 - **TRIE 树(K 叉)**：字典树的一种形式，用于字符串的存储和检索。 - **TRIE 树(左儿子右兄弟)**：另一种形式的字典树，通过左儿子右兄弟链接结构来实现。 - **后缀数组 O(N * LOG N)**：用于存储字符串的所有后缀按字典序排序的结果。 - **后缀数组 O(N)**：更高效的后缀数组构建方法。 - **RMQ 离线算法 O(N*LOGN)+O(1)**：用于求解区间最小值或最大值问题。 - **RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法 (O(NLOGN + Q))**：区间最小值或最大值查询的另一种实现方式。 - **RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA**：使用 RMQ 算法求解最近公共祖先问题。 - **LCA 离线算法 O(E)+O(1)**：另一种求解最近公共祖先问题的方法。 - **带权值的并查集**：支持带有权值的并查集操作。 - **快速排序**：一种常用的排序算法，平均时间复杂度为 O(n log n)。 - **2 台机器工作调度**：解决两个机器上的任务调度问题。 - **比较高效的大数**：支持大整数运算的实现。 - **普通的大数运算**：基本的大整数运算实现。 - **最长公共递增子序列 O(N^2)**：寻找两个序列中最长的公共递增子序列。 - **0-1 分数规划**：在 0-1 约束下的分数规划问题。 - **最长有序子序列（递增/递减/非递增/非递减）**：寻找序列中最长的递增、递减、非递增或非递减子序列。 - **最长公共子序列**：寻找两个序列的最长公共子序列。 - **最少找硬币问题（贪心策略-深搜实现）**：解决找零钱问题，通过贪心策略结合深度优先搜索。 - **棋盘分割**：解决棋盘分割问题。 - **汉诺塔**：解决汉诺塔问题。 - **STL 中的 PRIORITY_QUEUE**：标准模板库中优先队列的使用。 - **堆栈**：使用数组或链表实现的栈。 - **区间最大频率**：查询区间内的元素出现的最大频率。 - **取第 K 个元素**：在未排序的数组中寻找第 K 大的元素。 - **归并排序求逆序数**：使用归并排序计算数组的逆序数。 - **逆序数推排列数**：通过逆序数推导排列数。 - **二分查找**：一种高效的查找算法。 - **二分查找（大于等于 V 的第一个值）**：特定形式的二分查找。 - **所有数位相加**：计算一个数的所有数位之和。 #### Number 数论 - **递推求欧拉函数 PHI(I)**：使用递推公式计算欧拉函数 PHI(i)。 - **单独求欧拉函数 PHI(X)**：单独计算某个数 x 的欧拉函数 PHI(x)。 - **GCD 最大公约数**：计算两个或多个整数的最大公约数。 - **快速 GCD**：更高效的计算最大公约数的方法。 - **扩展 GCD**：不仅计算最大公约数，还求解 ax + by = gcd(a, b) 的整数解。 - **模线性方程 A * X = B (% N)**：求解形如 ax ≡ b (mod n) 的线性同余方程。 - **模线性方程组**：求解模线性方程组。 - **筛素数 [1..N]**：使用埃拉托斯特尼筛法筛选出 [1, N] 范围内的所有素数。 - **高效求小范围素数 [1..N]**：更高效地求解小范围内的素数。 - **随机素数测试(伪素数原理)**：通过概率性方法测试一个数是否为素数。 - **组合数学相关**：与组合数学相关的算法和公式。 - **POLYA 计数**：Polya 定理在计数组合问题中的应用。 - **组合数 C(N, R)**：计算组合数 C(n, r)。 - **最大 1 矩阵**：寻找最大全 1 子矩阵。 - **约瑟夫环问题（数学方法）**：通过数学方法解决约瑟夫环问题。 - **约瑟夫环问题（数组模拟）**：通过数组模拟解决约瑟夫环问题。 - **取石子游戏 1**：解决一类取石子游戏问题。 - **集合划分问题**：解决集合的划分问题。 - **大数平方根（字符串数组表示）**：计算大数的平方根。 - **大数取模的二进制方法**：计算大数取模的二进制方法。 - **线性方程组 A[][]X[]=B[]**：求解线性方程组。 - **追赶法解周期性方程**：解决周期性方程。 - **阶乘最后非零位,复杂度 O(NLOGN)**：计算阶乘的最后非零位数。 - **递归方法求解排列组合问题** - **类循环排列**：求解类循环排列问题。 - **全排列**：生成所有可能的排列。 - **不重复排列**：生成不重复元素的所有排列。 - **全组合**：生成所有可能的组合。 - **不重复组合**：生成不重复元素的所有组合。 #### 模式串匹配问题总结 - **字符串 HASH**：用于字符串匹配问题。 - **KMP 匹配算法 O(M+N)**：Knuth-Morris-Pratt 算法用于字符串匹配。 - **KARP-RABIN 字符串匹配**：Karp-Rabin 算法用于字符串匹配。 - **基于 KARP-RABIN 的字符块匹配**：基于 Karp-Rabin 算法的字符块匹配。 - **函数名: STRSTR**：C/C++ 标准库中的字符串查找函数。 - **BM 算法的改进的算法 SUNDAY ALGORITHM**：Sunday 算法对 Boyer-Moore 算法的改进。 - **最短公共祖先（两个长字符串）**：寻找两个长字符串的最短公共祖先。 - **最短公共祖先（多个短字符串）**：寻找多个短字符串的最短公共祖先。 #### Geometry 计算几何 - **GRAHAM 求凸包 O(N * LOGN)**：Graham 算法用于求解凸包问题。 - **判断线段相交**：判断两条线段是否相交。 - **求多边形重心**：计算多边形的质心。 - **三角形几个重要的点**：介绍三角形中的一些特殊点。 - **平面最近点对 O(N * LOGN)**：求解平面上最近点对的问题。 - **LIUCTIC 的计算几何库**：提供了一系列计算几何的基本操作。 - **求平面上两点之间的距离**：计算平面上两点之间的距离。 - **(P1-P0)*(P2-P0)的叉积**：计算向量叉积。 - **确定两条线段是否相交**：判断两条线段是否相交。 - **判断点 P 是否在线段 L 上**：判断一个点是否位于一条线段上。 - **判断两个点是否相等**：判断两个点是否相等。 - **线段相交判断函数**：用于判断两条线段是否相交的函数。 - **判断点 Q 是否在多边形内**：判断一个点是否位于一个多边形内部。 - **计算多边形的面积**：计算多边形的面积。 - **解二次方程 AX^2+BX+C=0**：求解一般形式的二次方程。 - **计算直线的一般式 AX+BY+C=0**：求解直线的一般式方程。 - **点到直线距离**：计算点到直线的距离。 - **直线与圆的交点，已知直线与圆相交**：求解直线与圆的交点。 - **点是否在射线的正向**：判断一个点是否位于射线的正方向上。 - **射线与圆的第一个交点**：求解射线与圆的第一个交点。 - **求点 P1 关于直线 LN 的对称点 P2**：求解一个点关于直线的对称点。 - **两直线夹角（弧度）**：计算两条直线的夹角。 以上概述了吉林大学计算机科学与技术学院2005级的 ACM/ICPC 代码库中所列出的算法和数据结构知识点，涉及图论、网络流、数据结构、数论以及计算几何等多个领域，为算法学习者提供了丰富的资源。