1922 - 네트워크 연결

각 컴퓨터를 연결하는데 필요한 비용이 주어질 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 구하는 문제이다.

모든 컴퓨터(모든 정점)을 연결하는 최소 스패닝 트리를 구하면 되므로, 크루스칼 알고리즘을 사용하면 된다.

#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[1001];
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 <= 1000; i++) {
		parent[i] = i;
	}
	for (int m = 0; m < M; m++) {
		int x = find(Edge[m].u);
		int y = find(Edge[m].v);
        // 해당 간선을 추가해도 사이클이 x이면
		if (x != y) {
			Union(x, y);
			ans += Edge[m].w;
		}
	}
	printf("%d", ans);
}