[boj : 16562] 친구비

www.acmicpc.net/problem/16562

16562번: 친구비

문제 : 친구를 만들고 싶은데 이때 비용이 든다. 친구의 친구도 친구가 된다. 가장 적은 비용을 사용해서 전부 친구로 만들 수 있도록 하여라.

 

해설 : 이런 문제의 특징은 꼭 친구의 친구까지 친구가 된다는 것. 이는 너 disjoint-set이라는 개념을 알고 있냐?! 라고 묻는 것 같다. union-find 자료구조를 사용해서 구하면 된다.

이때, 주의할 점은 부모들을 한쪽으로 몰아주어야 된다는 것이다.

만약,

1-3 

4-5

3-4

이렇게 들어오게 되면 1 3 4 5 전부 부모들이 같지만 통일 시켜주지 않으면 부모들을 저장하고 있는 배열에서 바로 가져올때 옳바르지 못한 과정이 되버린다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int parent[10001],v[10001];
int f[10001],A[10001];

void union_parent(int x, int y);
int get_parent(int x);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> f[i];
		parent[i] = i;
		A[i] = (int)1e9;
	}
	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		union_parent(x, y);
	}
	for (int i = 1; i <= n; i++) {
		x = get_parent(i);
		A[x] = min(A[x], f[i]);
	}
	int sum = 0;
	for (int i = 1; i <= n; i++)
		if (A[i] != (int)1e9)
			sum += A[i];
	//for (int i = 1; i <= n; i++)
	//	cout << A[i] << " ";
	if (sum <= k)cout << sum;
	else cout << "Oh no";
	return 0;
}
void union_parent(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);
	
	if (x < y)
		parent[y] = x;
	else
		parent[x] = y;
}
int get_parent(int x)
{
	if (x == parent[x])return x;
	return parent[x] = get_parent(parent[x]);
}