[백준 문제풀이] 백준 16562 c++ 친구비

 

유니온 파인드 알고리즘 (최적화 사용)

 

- 유니온 파인드의 최적화를 활용

부분집합을 union 할때 (합칠 때) 작은 값을 가진 노드를 루트로 설정하면서 합쳐야 함

 

=> 값을 가진 배열과 유니온 배열을 분리해서 생성

 

놓였던 점:

각각의 부분집합의 루트를 구하는, 코드의 마지막 부분에서 구현이 부족했다.

find 함수를 이용하기 보다는 이전에 bool 형으로 루트만을 false 해주는 형식으로 하여, 친구 관계의 input이 없는 노드에 대해서 처리를 하지 못했다.

 

개선할 부분이 있다면, 이런 방식보다는 최종 최소 값을 구하는 과정에서 bool형을 활용하여 find와 같이 쓰는 것이 더 일반적으로 보일 수 있다.

 

#include <iostream>

int f[10001] = {};
int a[10001] = {};
bool check[10001] = {};
void init(int n) {
	for (int i{ 0 }; i <= n; i++) {
		f[i] = i;
	}
}

int find(int n) {
	if (f[n] == n) return n;
	else return find(f[n]);
}

void merge(int b, int c) {
	b = find(b);
	c = find(c);
	if (b == c) {
		check[b] = false;
	}	
	else {
		if (a[b] < a[c]) {
			f[c] = b;
			check[b] = false;
			check[c] = true;
		}
		else {
			f[b] = c;
			check[c] = false;
			check[b] = true;
		}
	}
}

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

	int n, m, k;
	std::cin >> n >> m >> k;

	init(n);

	for (int i{ 1 }; i <= n; i++) {
		std::cin >> a[i];
	}

	int b, c;
	for (int i{ 0 }; i < m; i++) {
		std::cin >> b >> c;
		merge(b, c);
	}

	int t = k;
	for (int i{ 1 }; i <= n; i++) {
		if (!check[i]) {
			k -= a[i];
			if (k < 0) {
				std::cout << "Oh no\n";
				return 0;
			}
		}
	}

	std::cout << t - k << "\n";
}