[백준/BOJ] 백준 16562번 : 친구비

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

16562번: 친구비

유니온 파인드를 이용해 문제를 해결했다. 친구 관계를 유니온 하였는데, 유니온 하면서 해당 그룹의 비용은 더 작은 값으로 하도록 만들어서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n, m, k;
vector<int> cost(10001);
vector<int> parent(10001);
vector<int> rank_size(10001, 1);
int result = 0;

void Pre()
{
	for (int i = 1; i <= n; i++)
		parent[i] = i;
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
		cost[v] = min(cost[u], cost[v]); //더 작은값으로 비용을 정한다
	}

	else
	{
		parent[v] = u;
		cost[u] = min(cost[u], cost[v]); //더 작은값으로 비용을 정한다

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}
}


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

	cin >> n >> m >> k;

	Pre();

	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;

		cost[i] = a;
	}

	for (int i = 0; i < m; i++)
	{
		int v, w;
		cin >> v >> w;

		Merge(v, w);
	}

	set<int> check;
	for (int i = 1; i <= n; i++)
	{
		int u = Find(i);

		if (check.count(u) == 0) //아직 안나온 그룹일때
		{
			result += cost[u];
			check.insert(u);
		}
	}

	if (result > k)
		cout << "Oh no";
	else
		cout << result;

	return 0;
}