[BOJ] 1922 : 네트워크 연결

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int n_ = 1e3 + 1;
const int m_ = 1e5 + 1;

struct node { int u, v, w; } edg[m_];
int p[n_];

inline int find(int u) {
	if (u == p[u]) return u;
	return p[u] = find(p[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (u > v) swap(u, v);
	p[u] = v;
}

int main() {
	int i, n, m, u, v, w, cnt = 0;

	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d", &u, &v, &w);
		edg[i].u = u, edg[i].v = v, edg[i].w = w;
	}
	
	sort(edg + 1, edg + m + 1, [](const node &i, const node &j){ return i.w < j.w; });
	
	long long ans = 0;
	for (i = 1; i <= n; i++) p[i] = i;
	for (i = 1; i <= m; i++) {
		u = find(edg[i].u), v = find(edg[i].v);
		if (u == v) continue;
		merge(u, v);
		ans += edg[i].w;
		if (++cnt == n - 1) break;
	}
	printf("%lld", ans);
	return 0;
}