Minimum spanning tree: Kruskal

Kruskal

The algorithm of adding edges one by one to generate the minimum spanning tree

Use Kruskal Concurrent search set is used

Initialize and query set , At the beginning, the representative yuan of all points is itself , Each point itself constitutes a set ;

Sort the edge weights from small to large ;

Enumerate all edges in the order of the edge weight from small to large , If the two vertices connected by the current edge are in the same set （ Their representative elements are the same ）, Then do nothing , otherwise

Add this edge to the edge set of the minimum spanning tree ;

Merge the set where the two points connected by this edge are located with the merge operation of the joint search set ;

Until only one set is left .

Time complexity ：$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;
}