Kruskal算法

求最小生成树有两种常见的算法：$\text{Prim}$ 和 $\text{Kruskal}$。
稠密图上前者快，否则后者快。
显然这道题不是稠密图，所以我使用了 $\text{Kruskal}$。
其实是我太蒻了，不会Prim

$\text{Kruskal}$ 的基本思想是贪心，对所有的边按边权进行排序，逐个判断，如果边的两端在新图中不连通，则将边加入新图。

通常使用并查集维护点的连通性。
基于并查集的 $\text{Kruskal}$ 算法如下。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;

struct ed{
	int u,v,w;
}e[200005];
int f[5005],n,m;

int find(int x){
	if(x!=f[x]) f[x] = find(f[x]);
	return f[x];
}

inline void merge(int x, int y){
	int fx=find(x), fy=find(y);
	if(fx!=fy) f[fx] = fy,n--;
}

bool cmp(ed x, ed y){
	return x.w<y.w;
}

int main(){
	cin >> n >> m;
	for(int i=1; i<=n; i++) f[i]=i;
	for(int i=1; i<=m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
	sort(e+1, e+1+m, cmp);
	int sum=0;
	for(int i=1; i<=m; i++){
		if(find(e[i].u)==find(e[i].v)) continue;
		sum+=e[i].w, merge(e[i].u,e[i].v);
		if(n==1) {cout << sum; return 0;}
	}
	cout << "orz";
    
    return 0;
}
'''