最小生成树个人喜欢 $Kruskal$ 算法

前置知识：贪心，并查集

原理

最小生成树：一个无向连通图，边权值和最小的生成树

既然是边权值和最小，那么我们可以用贪心的思想，将边权从小到大排序，依次插入最小生成树中。

这是具体的排序后插入的操作：

1. 如果 $u$，$v$ 两点之间没有路径，我们就将这条边加入到最小生成树中；
2. 如果 $u$，$v$ 两点之间已经在最小生成树中有路径，或者形成了一个环，那么我们就把这条边"扔掉"。

重复以上步骤，我们可以顺便统计最小生成树的边权和，直到最小生成树中有 $n-1$ 条边(也就是构成了一棵树)。

至于实现有无路径，我们可以使用并查集实现。

这样子的时间复杂度最优是 $O(m \log{m})$

注意!!! 开long long!!!，$0 \le w_i \le 10^6$!!!

这里提一嘴另一种求解最小生成树的方式:Prim，题解(link)可以参考楼下的 xiaoququ 大佬。

它与 $Kruskal$ 的区别就在于一个是加点(Prim)，一个是加边(Kruskal)，而且 Prim 类似于最短路中的 Dijsktra 算法。

AC code

// Kruskal
const int N = 2e5 + 5;
typedef long long ll;

struct Edge{
	ll u, v, w;
}e[N];

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

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

int main(){

	sort (e + 1, e + m + 1, cmp);
	ll cnt = 0;
	int tot = 0;
	for (int i = 1; i <= m; ++i){
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int fu = find(u), fv = find(v);
		
		if (fv == fu) continue;
		fa[fu] = fv;
		tot++;
		cnt += w;
		if (tot == n - 1) break;
	}
	return 0;
}