백준 16562, 친구비

 

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

16562번: 친구비

요약

 

 

초기에 다른 모든 정점과 단절된 한 정점이 존재한다. 그 정점에서 다른 모든 정점에 간선을 잇는 비용이 주어질 때, 연결그래프를 만들기 위한 최소 비용을 구한다.

---

1. 이미 연결되어 있는 M개의 간선 정보가 주어진다. 단절된 정점에서 한 정점과 간선을 연결하면 그 정점과 연결된 모든 정점과도 연결되기 때문에, 이미 연결된 두 정점에 대해서 Union 연산을 수행하여 비용이 더 작은 쪽으로 합쳐준다.

 

2. 단절된 정점을 0번 노드로, 친구 노드를 1 ~ N번 노드로 설정한 뒤, 모든 정점을 Union 연산하며 그 비용을 K와 비교하여 정답을 출력한다.

#include <bits/stdc++.h>
using namespace std;

int N, M, K, cost;
int arr[10001];
int parent[10001];

int Find(int node);
void Union(int A, int B);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		parent[i] = i;
	}
	for (int i = 0; i < M; i++) {
		int v, w;
		cin >> v >> w;
		v = Find(v);
		w = Find(w);
		Union(v, w);
	}
	for (int i = 1; i <= N; i++) {
		int me = Find(0);
		int now = Find(i);
		if (me == now) continue;
		Union(me, now);
		cost += arr[now];
	}
	if (cost > K) cout << "Oh no";
	else cout << cost;
	return 0;
}

int Find(int node) {
	if (node == parent[node]) return parent[node];
	else return parent[node] = Find(parent[node]);
}

void Union(int A, int B) {
	A = Find(A);
	B = Find(B);
	if (A == B) return;
	if (arr[A] > arr[B]) parent[A] = B;
	else parent[B] = A;
	return;
}