# 定义及性质

如果连通图的一个子图是一棵包含所有顶点的树，则该子图称为其的生成树。

生成树是连通图的包含图中的所有顶点的极小连通子图，无环，只有 $n-1$ 条边。

图的生成树不唯一。从不同的顶点出发进行遍历，可得到不同的生成树。

无向连通图的最小生成树为边权和最小的生成树。

# 算法实现

常见的最小生成树算法有 Kruskal 算法和 Prim 算法。

Kruskal 的时间复杂度为 $O(m\log m)$ ，适合稀疏图。

暴力 Prim 的时间复杂度为 $O(n^2+m)$ ，适合于稠密图。

堆优化 Prim 类似 Dijkstra 的堆优化，但如果使用二叉堆等不支持 $O(1)$ decrease-key 的堆，复杂度就不优于 Kruskal ，常数也比 Kruskal 大。

一般情况下使用 Kruskal 算法。在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但不一定实际跑得更快。

Kruskal 算法能在 $O(m\log m)$ 的时间内得到一个最小生成树，主要是基于贪心的思想：

由于只需要维护连通性，不需要真正建立图 $T$ ，可用并查集来维护。

$Code:$

	#include<bits/stdc++.h>
	using namespace std;

	const int N = 1e6;
	int n, m, f[N], sum, num;
	struct edge
	{
	int u, v, w;
	} e[N];

	int read()
	{
	int x = 0; bool s = 0; char c = getchar();
	while(c < '0' \|\| c > '9') {if(c=='-') s = 1; c = getchar();}
	while('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
	return s ? -x : x;
	}

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

	int find(int x) {return f[x] == x ? f[x] : f[x] = find(f[x]);}

	bool Kruskal()
	{
	sort(e + 1, e + m + 1, cmp); // 将边权排序
	for(int i = 1; i <= m; i++)
	{
	int x = find(e[i].u), y = find(e[i].v);
	if(x == y) continue; // 若两点已经联通，则不需要这条边
	f[x] = y;
	sum += e[i].w;
	if(++num == n - 1) return true; // 若已构成一颗树，即边数为点数减一时，退出操作
	}
	return false;
	}

	int main()
	{
	n = read(), m = read();
	for(int i = 1; i <= n; i++) f[i] = i; // 初始化并查集
	for(int i = 1; i <= m; i++) e[i].u = read(), e[i].v = read(), e[i].w = read();
	if(Kruskal()) printf("%d", sum);
	else puts("orz");
	return 0;
	}