백준 16562번 친구비 C++

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

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k;

vector<int> parent;
vector<int> height;

struct Info {
	int index;
	int cost;
	bool operator<(const Info& other) const {
		return cost < other.cost;
	}

	bool operator>(const Info& other) const {
		return cost > other.cost;
	}
};

vector<Info> infos;

int GetParent(int n) {
	if (n == parent[n]) return n;
	return parent[n] = GetParent(parent[n]);
}

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

	if (u == v) return;

	if (height[u] > height[v])
		::swap(u, v);

	parent[u] = v;

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

int main()
{
	cin >> n >> m >> k;
	parent = vector<int>(n + 1);
	height = vector<int>(n + 1, 1);
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		int cost;
		cin >> cost;
		infos.push_back({ i,cost });
	}
	sort(infos.begin(), infos.end());

	int ans = 0;
	for (int i = 0; i < m; i++) {
		int v, w;
		cin >> v >> w;
		Merge(v, w);
	}
	vector<int> found(n + 1, false);
	for (auto a : infos) {
		int parent = GetParent(a.index);
		if (found[parent]) continue;
		found[parent] = true;
		ans += a.cost;
	}
	if (ans <= k) {
		cout << ans;
	}
	else {
		cout << "Oh no";
	}
}