kruskal算法

需要的东西：
1. p[N] - 搭配find()方法使用：查找根节点
2. Edge结构题 ： 存储起点，终点，边权值
3. cmp方法 ： 专门为Edge结构题编写的排序方法，搭配sort()使用，从小到大排序。

算法思想：

• 遍历每一条边，如果边的两点不属于同一个集合（即他们的根结点不同），就采纳这条边，把这条边加入到我们的结果中。然后把这两个节点其中一个的根结点的父节点改为另外一个节点的根结点。从而这两个节点的根结点都是同一个了。遍历完所有的边或者中途就发现已经采纳n-1条边了就直接停止（共n个节点）。如果遍历完之后发现采纳边数少于n-1条，发现图中有节点没有连通。

• 关于find查找根结点的方法实现思路是：借助p数组，p数组存储每个节点的父亲节点。如果p[i] = i的话，只有根节点的父亲节点才是自己。借助这个特性，遍历出根节点，递归搜索。

• 还要给Edge结构体专门写一个cmp函数，否则不能使用sort函数。

#include <bits/stdc++.h>
using namespace std;

const int N = 510,M = 100010,INF = 0x3f3f3f3f;
int res = 0;
int p[N];

struct Edge{
    int a,b,c; //a为起点，b为终点，c为权值
}e[M];//存储边信息的结构体

bool cmp(Edge a,Edge b) //给Edge重写一个专属的排序算法，从小到大排
{
    return a.c < b.c;
}

int find(int x)  //并查集，查找根节点
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n , m;
    cin >> n >> m;
    int cnt = n;


    for(int i = 0 ; i < m; i++)
        cin >> e[i].a >> e[i].b >> e[i].c;

    for(int i = 1 ; i <= n ; i++)   
        p[i] = i;

    sort(e,e+m,cmp); // 给sort用上我们刚写的edge专属排序方法

    for(int i = 0; i < m; i++) // 遍历每一条边
    {
        int a = e[i].a; //起点
        int b = e[i].b; //终点
        if(find(a) != find(b))
        {
            p[find(b)] = find(a);  //如果取了边，则让其中一个点的根节点的父节点变成另一个点的根节点
            cnt--;                 
            res+= e[i].c;
        }
    }
    if(cnt>1) cout << "impossible";  
    else cout << res << endl;


    return 0;
}