最小生成树：Kruskal

Kruskal

一条条添加边生成最小生成树的算法

使用Kruskal使用了并查集

初始化并查集，一开始所有的点的代表元都是它自己，每个点本身构成一个集合；

将边权从小到大的顺序排序；

按边权从小到大的顺序依次枚举所有的边，如果当前这条边连接的两个顶点位于同一集合（它们的代表元是一样的），则什么都不做，否则

将这条边添加到最小生成树的边集里；

用并查集的合并操作将这条边连接的两个点所在的集合合并；

直到只剩下一个集合结束。

时间复杂度：$O(mlogn)$

struct Node
{
    int x, y, v;

    bool operator<(const Node &A) const
    {
        return v < A.v;
    }
} a[M];

int n, m, fa[N];

int findest(int i)
{
    if (i == fa[i])
        return i;
    return fa[i] = findest(fa[i]);
}

int Kruskal()
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    sort(a + 1, a + m + 1);
    int ans = 0, cnt = n;
    for (int i = 1; i <= m; i++)
    {
        int x = findest(a[i].x), y = findest(a[i].y);
        if (x != y)
        {
            fa[x] = y;
            ans += a[i].v;
            --cnt;
        }
        if (cnt == 1)
            break;
    }
    if (cnt != 1)
        return -1;
    else
        return ans;
}