1197 - 최소 스패닝 트리

1<=V<=10000인 정점과 1<=E<=100,000인 간선이 주어졌을 때 최소 스패닝 트리를 구하는 문제이다.

크루스칼 알고리즘을 구현하여 제출하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
	int u, v, w;
	// 구조체 edge에서의 연산자 < 정의
	bool operator < (const edge &other) {
		return w < other.w;
	}
};
int parent[10001];
int find(int x) {
	if (x == parent[x]) {
		return x;
	}
	return parent[x] = find(parent[x]);
}
void Union(int x, int y) {
	x = find(x);
	y = find(y);
	parent[y] = x;
}
int main()
{
	// 컴퓨터의 수 N, 연결할 수 있는 선의 수 M
	int N, M;
	cin >> N >> M;
	vector<edge> Edge;
	int ans = 0;

	for (int m = 0; m < M; m++) {
		int a, b, c;
		cin >> a >> b >> c;
		Edge.push_back({ a, b, c });
	}
	sort(Edge.begin(), Edge.end());
	for (int i = 1; i <= 10000; i++) {
		parent[i] = i;
	}
	for (int m = 0; m < M; m++) {
		int x = find(Edge[m].u);
		int y = find(Edge[m].v);
		if (x != y) {
			Union(x, y);
			ans += Edge[m].w;
		}
	}
	printf("%d", ans);
}