最小生成树

一个定理：必定包含权值最小的边
不然把小边加入，删除环上任何一条边结果都更优
两个算法：

1. Kruskal
   贪心算法，每次判断最短的边加入是否会形成环，用并查集判断
   可以加就加入

const int N = 200010 ;
const int M = 500010 ;


int n, m ;
int fa[N] ;

struct edge {
	int x, y, z ;
	friend bool operator < (const edge &a, const edge &b) {
		return a.z < b.z ;
	}
} a[M] ;

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

void merge(int x, int y) {
	fa[x] = y ;
}
int main() {
	scanf("%d%d", &n, &m) ;
	for (int i = 1; i <= m; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z) ;
	sort(a + 1, a + m + 1) ;
	for (int i = 1; i <= n; i++) fa[i] = i ;
	ll ans = 0 ;
	for (int i = 1; i <= m; i++) {
		int x = get(a[i].x), y = get(a[i].y) ;
		if (x == y) continue ;
		merge(x, y) ;
		ans += a[i].z ;
	}
	printf("%lld\n", ans) ;
}