🖊️ 문제

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

---

🖊️ 풀이

친구로 연결된 애들은 하나.

1. 연결된 친구들의 집합으로 나눈다.
2. 각 집합에서 가장 적은 친구비를 가진 친구를 찾는다.

일단 1번은 그래프의 각 연결 요소들을 찾으면 된다.

연결요소란 그래프 내에서 나누어진 각각의 그래프를 의미한다.
참고 : 이전에 풀었던 연결요소 구하는 문제 백준 11724

그래서 일단,
DFS를 이용해서 각 연결요소들로 나눠서 구한다.

그리고 각 연결요소들을 구하는 과정에서 최소 친구비를 구하고,

연결요소가 분리되면 최소 친구비를 최종 친구비에 추가한다.

그렇게 풀면 끝!

골드4지만 쉬웠던..

1트+15분컷 굿굿

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

int arr[10001];
vector<vector<int>> vec;
bool visited[10001] = { false, };
int tempCost = 987654321;
int cost = 0;

void DFS(int cur)
{
	visited[cur] = true;
	tempCost = min(tempCost, arr[cur]);
	for (int i = 0; i < vec[cur].size(); i++) {
		if (!visited[vec[cur][i]]) DFS(vec[cur][i]);
	}
}

int main()
{
	int n, m, k;
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];

	for (int i = 0; i <= n; i++)
		vec.emplace_back(vector<int>());

	int v, w;
	for (int i = 0; i < m; i++) {
		cin >> v >> w;
		vec[v].emplace_back(w);
		vec[w].emplace_back(v);
	}

	int idx = 0;
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			DFS(i);
			cost += tempCost;
			tempCost = 987654321;
		}
	}

	if (cost <= k) cout << cost << endl;
	else cout << "Oh no" << endl;
}