ACM竞赛必备：图算法与Prim最小生成树模板

"ACM常用算法集，ACMer必备" 在ACM竞赛中，掌握一系列常用的算法是至关重要的，这些算法通常包括图算法、排序、搜索、动态规划等。以下是两个在ACM竞赛中常见的图算法——Kruskal's Algorithm（克鲁斯卡尔算法）和Prim's Algorithm（普里姆算法）的实现。 1. Kruskal's Algorithm（克鲁斯卡尔算法）： 克鲁斯卡尔算法是一种用于寻找加权无向图的最小生成树的算法。其基本思想是从边的集合中选择权重最小的边，并检查这条边是否与已经选择的边构成环路。如果不会形成环路，就将这条边添加到最小生成树中。在提供的代码中，首先读取边的数量和节点数，然后对所有边按权重进行排序。接着，使用并查集（Disjoint Set）数据结构来判断新加入的边是否会形成环路。在并查集中，`uni`函数用于合并两个集合，并确保在合并过程中保持集合的树状结构以优化查找效率。最后，输出最小生成树中最重的边的权重。 2. Prim's Algorithm（普里姆算法）： 普里姆算法是另一种用于寻找最小生成树的方法，它从一个节点开始，逐步增加边，直到覆盖整个图。在这个过程中，始终保持一个以已选择节点为顶点的子图，使得这个子图是一个树且所有边的权重之和最小。提供的代码中，使用邻接矩阵`g`来存储图的信息，初始化时设置每个节点为一个独立的集合。接着，使用Prim算法逐步扩展最小生成树，每次选择与当前树连接且权重最小的边。同样，这里使用了并查集来快速检测新边是否会形成环路。在找到n-1条边后，最小生成树构建完成，输出最小生成树中权重最大的边作为结果。 这些算法的实现都需要高效的数据结构和操作，如并查集，以及对图理论的理解。在ACM竞赛中，熟练掌握这些算法有助于解决涉及图的题目，提高解题速度和正确率。同时，了解如何优化代码以适应在线判题系统的时间限制也是ACMer必须具备的技能。