ACM（国际大学生程序设计竞赛，International Collegiate Programming Contest）是全球范围内的一项重要赛事，旨在锻炼和提升大学生的算法设计和编程能力。在ACM竞赛中，掌握一系列经典的算法模板对于解决问题至关重要。以下是一些ACM算法模板的详细说明：
1. **深度优先搜索(Depth First Search, DFS)**: DFS是一种遍历或搜索树或图的方法，常用于解决图论中的问题，如判断强连通分量、寻找欧拉路径等。在DAG（有向无环图）中，可以进行深度优先搜索标记，用于检测环路。
2. **桥找寻**: 在无向图中，桥是指删除后会使得图不连通的边。可以通过DFS来找出图中的所有桥。
3. **连通度(割)**: 无向图的连通度表示将图分割成两个非空子集所需的最少边数，可以使用DFS计算。
4. **最大团问题**: 这是一个NP完全问题，可以采用动态规划（DP）和DFS结合的方式求解，寻找一个图中最大的完全子图。
5. **欧拉路径**: 如果图中每个边恰好被访问一次，那么存在一个欧拉路径。可以使用DFS找到这样的路径，时间复杂度为O(E)，其中E为边的数量。
6. **Dijkstra算法**: Dijkstra算法用于求解单源最短路径问题。数组实现的时间复杂度为O(N^2)，而优先队列（如二叉堆）实现的时间复杂度为O(E * LOG E)，其中N是顶点数，E是边数。
7. **Bellman-Ford算法**: 可处理负权边，寻找单源最短路径，时间复杂度为O(VE)。
8. **SPFA（Shortest Path Faster Algorithm）**: 是一种改进的Dijkstra算法，适用于处理负权边，但可能会出现慢的情况。
9. **第K短路**: 可以使用Dijkstra或A*算法进行扩展来找到第K条最短路径。
10. **Prim算法**: 求最小生成树（MST），用于连接所有顶点的最小权值树。时间复杂度为O(E log V)或O(V^2)，其中V是顶点数，E是边数。
11. **次小生成树**：在无向图中，可能存在多个生成树，Prim算法可以找到最小生成树，但次小生成树可能需要其他方法解决，如Kruskal算法的变种。
12. **最小生成森林问题**：当图中存在负权边时，可能需要找到最小生成森林，可以使用Kruskal或Floyd-Warshall算法。
13. **有向图最小树形图**：最小Steiner树问题，寻找连接特定顶点子集的最小权值树，通常使用贪心算法或动态规划解决。
14. **TARJAN强连通分量**：通过深度优先搜索确定图中的强连通分量。
15. **弦图判断**：弦图是指在平面图中，每条边都不穿过任何其他边的图。弦图的完美消除顺序可以用来解决某些图论问题。
16. **稳定婚姻问题(Gale-Shapley算法)**：这是一个匹配问题，可以使用稳定婚姻算法在O(N^2)时间内找到稳定匹配。
17. **拓扑排序**：对有向无环图进行排序，使得对于每一条有向边 (u, v)，节点u都在节点v之前。可以使用DFS或BFS实现。
18. **无向图连通分支**：使用DFS或BFS可以找出图的连通分支。
19. **有向图强连通分支**：同样，可以使用DFS找出有向图的强连通分量。
20. **有向图最小点基**：寻找图中最小的点集，使得从每个顶点出发都能到达这个点集中的某个点。可以使用DFS在邻接矩阵上实现。
21. **Floyd-Warshall算法**：求解所有顶点对之间的最短路径，时间复杂度为O(V^3)。
22. **2-SAT问题**：这是一个逻辑满足问题，可以使用回溯法或二分图的性质在O(2^N)时间内解决，其中N是变量数。
这些算法模板在ACM竞赛中非常常见，掌握它们对于提高解题效率至关重要。在实际编程过程中，需要根据具体问题选择合适的算法，并进行适当的优化以满足时间和空间复杂度的要求。
