題目：（來源：AcWing）

給定一個?n?個點?m?條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。

求最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出?impossible。

給定一張邊帶權的無向圖?G=(V,E)，其中?V?表示圖中點的集合，E?表示圖中邊的集合，n=|V|，m=|E|。

由?V?中的全部?n?個頂點和?E?中?n?1?條邊構成的無向連通子圖被稱為?G?的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖?G?的最小生成樹。

輸入格式

第一行包含兩個整數?n?和?m。

接下來?m 行，每行包含三個整數 u,v,w，表示點?u?和點?v?之間存在一條權值為?w?的邊。

輸出格式

共一行，若存在最小生成樹，則輸出一個整數，表示最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出?impossible。

數據范圍

1≤n≤105,
1≤m≤2?105,
圖中涉及邊的邊權的絕對值均不超過?1000。

輸入樣例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

輸出樣例：

6

kruskal算法思路：

1. 每次聯通一條最短邊，加n-1次， 如果邊的兩給節點已經聯通，則無需再加。

2. 查找兩個點是否在同一個聯通集合，需要用到并查集

3. 如果加入邊的數量<n-1，則說明無法生成最小生成樹。

代碼實現：

#include<iostream>
#include<algorithm>
using namespace std;const int N = 100020,M = 200020;//定義邊
struct Edge{int a,b,w;bool operator<(const Edge& edge){return w<edge.w;}
};int n,m;
int p[N];//并查集的集合
Edge edge[M];//邊的集合int find(int x)//并查集的find函數
{if(p[x]!=x) p[x]=find(p[x]);//遞歸的同時壓縮路徑，提高效率return p[x];//直接返回所在集合編號
}int kruskal()
{int res=0,nums=0;//res記錄最小樹權和，num記錄聯通邊數for(int i = 0;i<m;i++){Edge temp = edge[i];int a=temp.a , b=temp.b , c = temp.w;a = find(a);b = find(b);if(a != b)//a,b不在一個聯通集合中{p[b] = a;//就把他們聯通res+=c;//加入這個最短邊nums++;//聯通邊數+1}}if(nums<n-1) return -1;return res;}int main()
{cin>>n>>m;for(int i = 1;i<=n;i++) p[i] = i;//初始化并查集for(int i = 0;i<m;i++)//初始化邊集{int x,y,z;scanf("%d%d%d",&x,&y,&z);edge[i] = {x,y,z};}//邊集升序排序sort(edge,edge+m);int t = kruskal();if(t==-1) cout <<"impossible"<<endl;else cout<<t<<endl;return 0;
}

參考：

B站@藍不過海呀

地址：?圖-最小生成樹-Prim(普里姆)算法和Kruskal(克魯斯卡爾)算法_嗶哩嗶哩_bilibili

?