Kruskal算法（克魯斯卡爾算法）

核心操作
1、將所有邊按權重大小 從小到大排序 O(mlogm)宝剖； 這部分是本算法的瓶頸 比較耗時
2拐袜、 枚舉每條邊a -b 權重為c
如果 a-b 不連通 則把這條邊加入集合中
（因為最小生成樹不能含有自環(huán)，如果a-b已經(jīng)連通幔亥，再加入這條邊就會形成自環(huán)）

并查集的操作來維護本算法

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

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;

    /* bool operator< (const Edge &W)const
     {
        return w < W.w;
     }*/
    Edge() {

        a = 0;
        b = 0;        //注意 荞怒，當寫了有參構造函數(shù)時刘绣，一定要加上無參構造函數(shù)，不然會編譯出錯
        w = 0;

    }
    Edge(int aa, int bb, int ww) {
        a = aa;
        b = bb;
        w = ww;
    }

}edges[M];

bool operator<(Edge A, Edge B) {

    return A.w < B.w;          //重載運算符 使用sort排序時一般重載小于號
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]); //并查集中的find函數(shù)
    return p[x];                    // 如果x不是祖宗節(jié)點 則繼續(xù)找祖宗節(jié)點 否則返回祖宗節(jié)點
}

int kruskal()
{
    sort(edges+1, edges + m+1);//注意 數(shù)組為1~m排序時  sort正常是0~n

    for (int i = 1; i <= n; i++) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 1; i <=m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);//找到a b的祖宗節(jié)點
        if (a != b)//如果祖宗節(jié)點不同 則說明他們不連通
        {
            p[a] = b; //將他們合并成一個集合
            res += w;//累加邊的權重值
            cnt++;//更新集合中已經(jīng)有的邊數(shù)
        }
    }

    if (cnt < n - 1) return INF;//n個點 一共有n-1 條邊 如果最后集合中的邊數(shù)小于n-1 則說明不能連通
    return res;// 圖可以連通 返回邊權和
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <=m; i++)  //結構體無向圖初始化方法 本體按有向圖初始化不影響最小生成樹
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = Edge(a, b, w);

    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}