[BOJ] 1197 : 최소 스패닝 트리

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

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

struct node {
	int u, v, c;
	bool operator <(node A)const { return c < A.c; }
} edg[m_];

int n, m;
int mom[n_];

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

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

int main() {
	int i;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++)
		scanf("%d %d %d", &edg[i].u, &edg[i].v, &edg[i].c);

	sort(edg + 1, edg + m + 1);

	long long ans = 0;
	for (i = 1; i <= n; i++) mom[i] = i;
	for (i = 1; i <= m; i++) {
		int u = find(edg[i].u), v = find(edg[i].v);
		if (mom[u] == mom[v]) continue;
		merge(u, v);
		ans += edg[i].c;
	}

	printf("%lld", ans);

	return 0;
}