[백준] 10423 - 전기가 부족해

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

10423번: 전기가 부족해

 

딱 보자마자 MST가 떠올랐지만, 특이한 부분이 있었다.

바로 문제에서 주어지는 YNY 발전소이다.

 

어떻게 할까 고민을 하다가, YNY 발전소로 주어지는 정점들을 모두 같은 부모(0번)로 지정해주어서,

미리 보이지 않는 간선으로 연결하였다.

 

이후에는 똑같이 MST를 구현하면 된다.

 

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

int n, m, k, parent[1001], y[1001];
vector<pair<int, pair<int, int>>> v;

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

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a < b) parent[a] = b;
	else parent[b] = a;
}

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

	for (int i = 1; i <= n; i++) parent[i] = i;

	for (int i = 0; i < k; i++) {
		int a; cin >> a;
		parent[a] = 0;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		v.push_back({ c,{a,b} });
	}

	sort(v.begin(), v.end());
	int ans = 0;

	for (auto& i : v) {
		int n1 = i.second.first;
		int n2 = i.second.second;
		int cost = i.first;

		int f1 = Find(n1);
		int f2 = Find(n2);

		if (f1 != f2) {
			Union(n1, n2);
			ans += cost;
		}
	}

	cout << ans;
}