[백준] 1922번 네트워크 연결

문제 출처: https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

MST를 구해서 가중치의 합을 구하는 문제입니다.

크루스칼 알고리즘에서 사이클이 생기지 않도록 간선을 정해야하기 때문에 같은 집합 여부를 확인하기 위해 유니온 파인드를 사용했다.

 

#include<iostream>
#include<queue>
#include<fstream>
#include<tuple>
#include<algorithm>

using namespace std;

struct P{
	int s, e, d=100000;
};
P arr[100000];

bool cmp(P a, P b) {
	return a.d < b.d;
}

int u[1001];

int find(int a) {
	if (u[a] < 0)return a;
	return u[a] = find(u[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	if (u[a] < u[b]) {
		u[a] += u[b];
		u[b] = a;
	}
	else {
		u[b] += u[a];
		u[a] = b;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	int M; cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[i] = P{ a,b,c };
	}

	sort(arr, arr + M,cmp);
	fill(u, u + 1001, -1);
	int sum = 0;
	int count = 0;
	for (int i = 0; i < M; i++) {
		if (count == N - 1)break;

		P curr = arr[i];
		if (find(curr.s) == find(curr.e))continue;
		
		merge(curr.s, curr.e);
		sum += curr.d;
		count++;
	}

	cout << sum;
}