[알고리즘] 백준 1922번: 네트워크 연결 (C++)

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

그래프에서 전체적인 관점에서 보았을 때, 가중치의 합들이 최소가 되게 하는 문제다.

>> MST 사용 >> 크루스칼

[AC 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX (100000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;

vector<pair<pii, ll>> edges;
int parent[MAX];
int n, m;

bool cmp(pair<pii, int> a, pair<pii, int> b) {
	return a.second < b.second;
}

int getRoot(int node) {
	if (parent[node] == node) {
		return node;
	}
	return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b) {
	if (getRoot(a) == getRoot(b)) {
		return true;
	}
	else return false;
}

void unionParent(int a, int b) {
	if (getRoot(a) < getRoot(b)) {
		parent[getRoot(b)] = getRoot(a);
	}
	else parent[getRoot(a)] = getRoot(b);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		edges.push_back({ {a, b}, w });
	}

	sort(edges.begin(), edges.end(), cmp);
	
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	int answer = 0;
	int cnt = 0;
	for (int i = 0; i < edges.size(); i++) {
		if (!find(edges[i].first.first, edges[i].first.second)) {
			unionParent(edges[i].first.first, edges[i].first.second);
			answer += edges[i].second;
		}
	}

	cout << answer;
	return 0;
}