kruskal 最小生成树

建最小生成树还有一个基于并查集的算法——kruskal算法

它的思路是从小到大枚举所有的边，如果这条边的两点的老祖宗不相等，这两点至少有一个不在树中，我们就把它算进去

时间复杂度是O(mlogm)，和H-prim一样。两者都适合用在稀疏图中，prim适合在稠密图

例题 洛谷 P3366 【模板】最小生成树

#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define forup(i, l, r) for(int i = l; i <= r; i++)
using namespace std;
const int N = 2e5 + 5;
struct edge{
	int u, v, w;
	bool operator < (edge e)
	{
		return w < e.w;
	}
}e[N];
int fa[N];
int n, m;
int sum;

int find(int a)
{
	return fa[a] == a? a: fa[a] = find(fa[a]);
}
bool kruskal()//稀疏图用kruskal或H-prim都可以 
{
	sort(e + 1, e + m + 1);
	forup(i, 1, n) fa[i] = i;
	
	int cnt = 0;
	forup(i, 1, m)
	{
		int x = find(e[i].u);
		int y = find(e[i].v);
		if(x != y)
		{
			fa[y] = x;
			sum += e[i].w;
			cnt++; 
		}
	}
	return cnt == n - 1;
} 
int main()
{
	cin>>n>>m;
	forup(i, 1, m)
	{
		int u, v, w;
		cin>>u>>v>>w;
		e[i] = {u, v, w};
	}
	if(kruskal())
	{
		cout<<sum;
	}
	else cout<<"orz";
	return 0;
}