[알고리즘] 백준 16202번: MST 게임 (C++)

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

16202번: MST 게임

MST의 조건인 간선의 개수가 N - 1이 되지 않는다면 0을 출력해주면 된다.

가중치가 작은 간선부터 제외시키는 방법은 for의 범위를 조금씩 높이면 된다.

[AC 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX (100000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;

vector<pair<pii, ll>> edges;
int parent[MAX];
int n, m, k;

bool cmp(pair<pii, int> a, pair<pii, int> b) {
	return a.second < b.second;
}

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

bool find(int a, int b) {
	if (getRoot(a) == getRoot(b)) {
		return true;
	}
	else return false;
}

void unionParent(int a, int b) {
	if (getRoot(a) < getRoot(b)) {
		parent[getRoot(b)] = getRoot(a);
	}
	else parent[getRoot(a)] = getRoot(b);
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		edges.push_back({ {a, b}, i + 1 });
	}

	sort(edges.begin(), edges.end(), cmp);
	for (int t = 0; t < k; t++) {

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

		int answer = 0;
		int cnt = 0;
		for (int i = t; i < edges.size(); i++) {
			if (!find(edges[i].first.first, edges[i].first.second)) {
				unionParent(edges[i].first.first, edges[i].first.second);
				answer += edges[i].second;
				cnt++;
			}
		}

		if (cnt == n - 1) cout << answer << ' ';
		else cout << 0 << ' ';
	}
	return 0;
}