Kruskal和prim不同的点在于prim每次都是找离集合距离最小的点，Kruskal找的是图中最短的边，如果边的两端不连通，则加入生成树中，属于是贪心的策略。

思路：

①每次都找最短的边，因此首先对所有的边进行从小到大的排序，因为排序，所以Kruskal的时间复杂度下限就已经是O(nlogn)了；

②判断两个点连不连通，直接使用并查集就可以了。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N = 2e5 + 9;
 6 int n,m,p[N],res,cnt;
 7 struct Edge
 8 {
 9     int a,b,w;
10     bool operator <(const Edge& W)
11     {
12         return w < W.w;
13     }
14 }edges[N];
15 
16 int find(int x)
17 {
18     if(p[x] != x)
19         p[x] = find(p[x]);
20     return p[x];
21 }
22 
23 int main()
24 {
25     cin >> n >> m;
26     for(int i = 0;i < m;++i)
27     {
28         int a,b,c;
29         cin >> a >> b >> c;
30         edges[i] = {a,b,c};
31     }
32     
33     for(int i = 1;i <= n;++i)
34         p[i] = i;
35     
36     sort(edges,edges + m);
37     
38     for(int i = 0;i < m;++i)
39     {
40         int a = edges[i].a,b = edges[i].b,w = edges[i].w;
41         int pa = find(a),pb = find(b);
42         if(pa != pb)
43         {
44             ++cnt;
45             res += w;
46             p[pa] = pb;
47         }
48     }
49     if(cnt < n - 1)
50         cout << "impossible" << endl;
51     else
52         cout << res << endl;
53     return 0;
54 }