[백준 16562] 친구비 (C++)

문제 링크: https://www.acmicpc.net/problem/16562

16562번: 친구비

1. 주의할 점

- 분리집합으로 집단을 나눈 이후, 그 집단에서 가장 작은 친구비를 더한다

 

2. 구현

- 입력을 받으면서 Par[](자신의 조상을 나타냄)배열을 초기화한다

- 친구 관계를 입력받을 때, 같은 집합이 형성되도록 Make_union() 함수를 사용한다. 그리고 Make_union() 함수를 사용할 때, 작은 친구비를 가진 학생이 해당 집합의 부모가 되도록 설정한다

- 0(이준석)번 학생과 친구가 되도록 친구가 되지 않은 집합들을 Make_union() 처리 + 친구비를 추가한다

- 친구비 > 수중에 가지고 있는 돈이라면 Oh no를, 아니라면 친구비를 출력한다

 

#include <iostream>
using namespace std;
int par[10001], price[10001], node, relation, money;
int find_par(int x) {
	if (par[x] == x) return x;
	return par[x] = find_par(par[x]);
}

void make_union(int a, int b) {
	a = find_par(a);
	b = find_par(b);
	if (a != b) {
		if (price[a] > price[b]) par[a] = b;
		else par[b] = a;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> relation >> money;
	for (int i = 1; i <= node; i++) {
		cin >> price[i];
		par[i] = i;
	}
	int a, b;
	price[0] = 987654321;
	for (int i = 0; i < relation; i++) {
		cin >> a >> b;
		make_union(a, b);
	}
	int result = 0;
	for (int i = 1; i <= node; i++) {
		int p = find_par(i);
		if (p != find_par(0)) {
			result += price[p];
			make_union(0, i);
		}
	}
	if (money >= result) cout << result;
	else cout << "Oh no";
	return 0;
}