ACM图论与数据结构算法详解

"MyLib(For+ACM)_内部资料" 是一份关于图论和数据结构的内部学习资料，主要涵盖了ACM/ICPC竞赛相关的算法和问题解决策略。这份资料由吉林大学ACMGroup1在2007年至2008年间编撰和修订，适用于计算机科学与技术领域的学习者。 ### 图论部分 1. **DAG的深度优先搜索标记**: 在有向无环图(DAG)中，深度优先搜索(DFS)用于标记节点，识别回路和计算拓扑排序。 2. **无向图找桥**: 找桥是指寻找那些移除后会增加连通分量的边，这通常通过Tarjan或Kosaraju算法实现。 3. **无向图连通度(割)**: 连通度是图的最大独立集大小，而割是将图分为两个非空部分所需的最少边数。 4. **最大团问题**：最大团问题是找到图中最大的完全子图，可以使用动态规划(DP)和深度优先搜索(DFS)来解决。 5. **欧拉路径**：在有向或无向图中，欧拉路径是从一个顶点出发并遍历所有边返回原点的路径，O(E)表示该算法的时间复杂度。 6. **Dijkstra算法**：用于找出图中从起点到所有其他点的最短路径，有两种实现方式：数组实现O(N^2)和优化后的O(E*logE)。 7. **Bellman-Ford算法**：单源最短路径算法，适用于包含负权边的图，时间复杂度为O(VE)。 8. **SPFA算法**：短路径更快算法，是Dijkstra算法的一种启发式改进，适用于某些情况下速度较快。 9. **第K短路**：找到图中除了最短路之外的第K条最短路径，可以使用Dijkstra或A*算法进行扩展。 10. **最小生成树**：包括Prim算法和Kruskal算法，用于寻找连通无向图中权重最小的边集合，形成一棵生成树。 11. **最小生成森林问题**：当图中有负权边时，需要寻找最小生成森林，如Kruskal's算法和Disjoint-set数据结构的优化实现。 12. **有向图最小树形图** 和 **MINIMAL STEINER TREE** 是解决特殊形式的最小生成树问题。 13. **TARJAN强连通分量**：识别有向图中的强连通分量，即每个节点都可以到达其他所有节点的子图。 14. **弦图判断** 以及 **弦图的PERFECT ELIMINATION点排列** 是弦图理论的一部分，涉及图的结构分析。 15. **稳定婚姻问题**：Gale-Shapley算法可以找到稳定匹配，时间复杂度为O(N^2)。 16. **拓扑排序** 和 **无向图连通分支**：在无向图中，拓扑排序是确定顶点的线性顺序，而连通分支使用DFS或BFS进行查找。 ### 数据结构部分 1. **求某天是星期几**：涉及到日期处理和日历算法。 2. **左偏树**：一种特殊的二叉堆，合并操作复杂度为O(logN)。 3. **树状数组**：又称二进制指数树，用于高效地进行区间更新和查询操作。 4. **二维树状数组**：对树状数组的扩展，处理二维区间问题。 5. **Trie树**：又称前缀树，用于高效存储和检索字符串。 6. **后缀数组**：用于快速处理字符串的后缀，有O(N*logN)和O(N)两种构建方法。 7. **RMQ（Range Minimum/Maximum Query）**：查找区间内最小或最大值的问题，离线和在线算法有不同时间复杂度。 8. **LCA（Lowest Common Ancestor）**：最近公共祖先问题，离线和在线算法有多种解决方案。 9. **带权值的并查集**：支持加权联合操作的并查集数据结构，用于维护树或图的联通性。 10. **快速排序**：高效的排序算法，平均时间复杂度为O(N*logN)。 11. **2台机器工作调度**：优化多任务分配，考虑最小化完成时间。 12. **大数运算**：高效处理大整数的加减乘除和比较，包括0-1分数规划问题。 13. **最长公共递增子序列**：找出两个序列中长度最长的公共递增子序列。 14. **0-1背包问题**：经典的组合优化问题，要求在容量限制下选择物品以最大化价值。 这些内容为参赛者提供了全面的图论和数据结构基础，帮助他们在ACM/ICPC等编程竞赛中解决各种复杂问题。