(BOJ) 1922 네트워크 연결

문제: https://www.acmicpc.net/problem/1922

 

문제 풀이:  mst 사용 ㅎㅎ

 

소스 코드:

typedef pair<int, pair<int, int>> P;
priority_queue<P, vector<P>, greater<P>> pq;
int n, m,cnt,p[1001],res;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;

	p[a] = b;
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;
	memset(p, -1, sizeof(p));

	for (int i = 0; i < m; i++) {
		int q, w, e;
		cin >> q >> w >> e;
		pq.push({ e,{q,w} });
	}
	while (!pq.empty()) {
		int cost = pq.top().first;
		int a = pq.top().second.first;
		int b = pq.top().second.second;
		pq.pop();

		if (merge(a, b)) {
			cnt++;
			res += cost;
			if (cnt == n - 1) break;
		}
	}
	cout << res<<"\n";
	return 0;
}