AcWing 859 Kruskal 算法求最小生成樹 題解 （Kruskal 算法求最小生成樹）

①Kruskal算法求最小生成樹思路：将m條邊排序，從最小的邊開始，判斷這條邊相連的兩個點是不是在一個連通塊内，如果是，就将這條邊舍棄（防止最小生成樹内形成環）， 如果不是，就将這條邊加入最小生成樹，所有邊都周遊之後，判斷最小生成樹内的邊的數量和總共的點的數量，最小生成樹應該是由n個點和n-1條邊構成，如果n-1>邊數，就代表這個圖不存在最小生成樹

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

using namespace std;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f;

int n, m;
int p[N];

struct Edge{//利用結構體儲存邊的兩個節點和權值 
	int a, b, w;
	
	bool operator < (const Edge & W) const //重載運算符，結構體内部排序 
	{
		return w < W.w;
	}
}edges[M];

int find(int x){//并查集找祖宗函數，判斷兩個點是否在一個連通快内 
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

int Kruskal(){
	
	sort(edges, edges + m);//先對邊按照權值進行排序 
	
	for(int i = 1; i <= n; i ++ ) p[i] = i;//初始化，每個節點都自成一個連通塊 
	
	int res = 0, cnt = 0;//res記錄最小生成樹的權值，cnt記錄最小生成樹的邊數 
	
	for(int i = 0; i < m; i ++ ){//周遊m條邊 
		int a = edges[i].a, b = edges[i].b, w = edges[i].w; 
		int a1 = find(a), b1 = find(b);//判斷這條邊的兩個節點在那個連通塊 
		
		if(a1 != b1){//如果這條邊的兩個節點不在一個連通塊内，這條邊就可以放進最小生成樹 
			p[a1] = b1;//将這兩個點放入一個連通塊内 
			cnt ++ ;//最小生成樹的邊數+1 
			res += w;//最小生成樹的權值和加上這條邊的權值 
		}
	}
	if(n - 1 > cnt) return INF;//如果圖的點數 -1>最小生成樹内的邊數，代表這個圖不存在最小生成樹 
	return res;//存在的話，傳回最小生成樹的權值和 
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	cin>>n>>m;
	for(int i = 0; i < m; i ++ ){
		int a, b, c;
		cin>>a>>b>>c;
		edges[i] = {a, b, c};
	}
	
	int t = Kruskal();
	
	if(t == INF) cout<<"impossible"<<endl;
	else cout<<t<<endl;
	
	return 0;
}