吉林大学ACM算法模板大全：图论、网络流、数据结构

ACM算法模板（吉林大学） ACM算法模板是计算机科学与技术学院的学生和ACM竞赛选手们不可或缺的参考指南。本文档涵盖了图论、网络流、数据结构等多个领域的重要算法和数据结构。 **图论** 图论是计算机科学中最重要的领域之一，涉及到图的遍历、搜索、最短路径、最小生成树等问题。本文档中，我们将讨论以下图论相关的知识点： * 深度优先搜索（DFS）：用于图的遍历，时间复杂度为O(E+V)。 * 无向图找桥：用于判断无向图中的桥边，时间复杂度为O(E+V)。 * 无向图连通度（割）：用于判断无向图的连通度，时间复杂度为O(E+V)。 * 最大团问题DP+DFS：用于解决最大团问题，时间复杂度为O(2^n)。 * 欧拉路径O(E)：用于判断欧拉路径，时间复杂度为O(E)。 * DIJKSTRA数组实现O（N^2）：用于解决单源最短路径问题，时间复杂度为O(N^2)。 * DIJKSTRAO(E*LOGE)：用于解决单源最短路径问题，时间复杂度为O(E*LOGE)。 * BELLMANFORD单源最短路O(VE)：用于解决单源最短路径问题，时间复杂度为O(VE)。 * SPFA(SHORTESTPATHFASTERALGORITHM)：用于解决单源最短路径问题，时间复杂度为O(E+N*LOGN)。 * 第K短路（DIJKSTRA）：用于解决第K短路问题，时间复杂度为O(N*LOGN)。 * 第K短路（A*）：用于解决第K短路问题，时间复杂度为O(N*LOGN)。 * PRIM求MST：用于解决最小生成树问题，时间复杂度为O(E*LOGE)。 * 次小生成树O(V^2)：用于解决次小生成树问题，时间复杂度为O(V^2)。 * 最小生成森林问题(K颗树)O(MLOGM)：用于解决最小生成森林问题，时间复杂度为O(MLOGM)。 * 有向图最小树形图：用于解决有向图最小树形图问题，时间复杂度为O(E+N*LOGN)。 * MINIMALSTEINERTREE：用于解决Steiner树问题，时间复杂度为O(E+N*LOGN)。 * TARJAN强连通分量：用于解决强连通分量问题，时间复杂度为O(E+N*LOGN)。 * 弦图判断：用于判断弦图，时间复杂度为O(E+N*LOGN)。 * 弦图的PERFECTELIMINATION点排列：用于解决弦图的PERFECTELIMINATION点排列问题，时间复杂度为O(E+N*LOGN)。 * 稳定婚姻问题O(N^2)：用于解决稳定婚姻问题，时间复杂度为O(N^2)。 * 拓扑排序：用于解决拓扑排序问题，时间复杂度为O(E+N*LOGN)。 * 无向图连通分支(DFS/BFS邻接阵)：用于解决无向图连通分支问题，时间复杂度为O(E+N*LOGN)。 * 有向图强连通分支(DFS/BFS邻接阵)O(N^2)：用于解决有向图强连通分支问题，时间复杂度为O(N^2)。 * 有向图最小点基(邻接阵)O(N^2)：用于解决有向图最小点基问题，时间复杂度为O(N^2)。 * FLOYD求最小环：用于解决最小环问题，时间复杂度为O(N^3)。 * 2-SAT问题：用于解决2-SAT问题，时间复杂度为O(N^2)。 **网络流** 网络流是计算机科学中的一种重要算法，涉及到最大流、最小割、最小费用流等问题。本文档中，我们将讨论以下网络流相关的知识点： * 二分图匹配（匈牙利算法DFS实现）：用于解决二分图匹配问题，时间复杂度为O(E+N*LOGN)。 * 二分图匹配（匈牙利算法BFS实现）：用于解决二分图匹配问题，时间复杂度为O(E+N*LOGN)。 * 二分图匹配（HOPCROFT－CARP的算法）：用于解决二分图匹配问题，时间复杂度为O(E+N*LOGN)。 * 二分图最佳匹配（KUHNMUNKRAS算法O(M*M*N)）：用于解决二分图最佳匹配问题，时间复杂度为O(M*M*N)。 * 无向图最小割O(N^3)：用于解决无向图最小割问题，时间复杂度为O(N^3)。 * 有上下界的最小(最大)流：用于解决有上下界的最小(最大)流问题，时间复杂度为O(E+N*LOGN)。 * DINIC最大流O(V^2*E)：用于解决最大流问题，时间复杂度为O(V^2*E)。 * HLPP最大流O(V^3)：用于解决最大流问题，时间复杂度为O(V^3)。 * 最小费用流O(V*E*F)：用于解决最小费用流问题，时间复杂度为O(V*E*F)。 * 最小费用流O(V^2*F)：用于解决最小费用流问题，时间复杂度为O(V^2*F)。 * 最佳边割集：用于解决最佳边割集问题，时间复杂度为O(E+N*LOGN)。 * 最佳点割集：用于解决最佳点割集问题，时间复杂度为O(E+N*LOGN)。 * 最小边割集：用于解决最小边割集问题，时间复杂度为O(E+N*LOGN)。 * 最小点割集（点连通度）：用于解决最小点割集问题，时间复杂度为O(E+N*LOGN)。 * 最小路径覆盖O(N^3)：用于解决最小路径覆盖问题，时间复杂度为O(N^3)。 * 最小点集覆盖：用于解决最小点集覆盖问题，时间复杂度为O(E+N*LOGN)。 **数据结构** 数据结构是计算机科学中的一种重要基础，涉及到数组、链表、树、图等数据结构。本文档中，我们将讨论以下数据结构相关的知识点： * 求某天是星期几：用于解决某天是星期几问题，时间复杂度为O(1)。 * 左偏树合并复杂度O(LOGN)：用于解决左偏树合并问题，时间复杂度为O(LOGN)。 * 树状数组：用于解决树状数组问题，时间复杂度为O(LOGN)。 * 二维树状数组：用于解决二维树状数组问题，时间复杂度为O(LOGN)。 * TRIE树(K叉)：用于解决TRIE树问题，时间复杂度为O(LOGN)。 * TRIE树(左儿子又兄弟)：用于解决TRIE树问题，时间复杂度为O(LOGN)。 * 后缀数组O(N*LOGN)：用于解决后缀数组问题，时间复杂度为O(N*LOGN)。 * 后缀数组O(N)：用于解决后缀数组问题，时间复杂度为O(N)。 * RMQ离线算法O(N*LOGN)+O(1)：用于解决RMQ问题，时间复杂度为O(N*LOGN)+O(1)。