Krusal算法二刷

408新大纲中新增了对并查集的考察，所以对于Kruskal算法使用了并查集的图论算法而言需要着重关注一下。

优点

只需要开个结构体数组存储所有的边即可，不需要使用 邻接表 或者 邻接矩阵 来表示整个图。代码量短。

代码思路：

对于所有边排序，这一步的时间复杂度是 $O(mlogm)$，从小到大依次遍历所有边，判断每个边的两个结点是否在同一个集合内部（并查集的应用），查询是否为同一个集合的时间复杂度是 $O(n)$，总的时间复杂度为 $O(mlogm)$.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e5 + 10;

// Kruskal算法只需要存储每条边的情况即可，不需要使用邻接表或者邻接矩阵
int n,m;
int p[N];
// 使用结构体存储每条边的情况
struct Edges {
    int a, b, w;        // 每条边的起点、终点、权重
    // 重载运算符
    bool operator< (const Edges& t) const {
        return w < t.w;
    }
}e[M];

// 并查集模板，判断两个结点是否在同一个集合
// 返回结点x的祖宗结点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);       // 路径压缩
    return p[x];
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        // 读入每条边的情况
        cin >> e[i].a >> e[i].b >> e[i].w;
    }
    // 按照边权的大小排序
    sort(e, e+m);

    // 并查集：初始化所有结点为独立的一个结合
    for (int i = 1; i <= n; i ++ ) p[i] = i; 

    // 记录已经使用的边的数量cnt和当前最小生成树的路径长度
    int cnt = 0, res = 0;
    // 从小到大遍历m条边
    for (int i = 0; i < m; i ++ )
    {
        // 取出每条边的相关信息
        int a = e[i].a, b = e[i].b, w = e[i].w;
        // 判断这条边的两个结点是否在同一个集合内
        a = find(a), b = find(b);
        if (a != b)
        {
            cnt ++;         // 已经使用的边的数量加一
            res += w;       // 将边权添加到结果中
            // 合并两个集合
            p[a] = b;       // 将结点a的祖宗节点更改为b的祖宗结点
        }
    }
    if (cnt == n-1) cout << res;
    else puts("impossible");

    return 0;
}