취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15809번 문제인 전국시대이다.
문제는 아래 링크를 확인하자.

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

문제에서 출력해야하는 내용을 잘 살펴보면 "서로 다른 나라들을 규칙에 따라 합쳐나가는" 시행을 빠르게 할 수 있는 disjoint set(union-find) 자료구조를 이용하여 문제를 해결할 수 있을 것임을 짐작할 수 있다.

나라를 합쳐나가면서, 나라의 인구 또한 쿼리에 맞게 같이 조절해나가는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int uf[100001];
int popul[100001];

int findf(int x) {
	if (uf[x] == x) return x;
	return uf[x] = findf(uf[x]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> popul[i];
	for (int i = 1; i <= N; i++) uf[i] = i;

	while (M--) {
		int x, a, b; cin >> x >> a >> b;
		a = findf(a), b = findf(b);
		if (x == 1) {
			popul[a] += popul[b];
			popul[b] = 0;
			uf[b] = a;
		}
		else {
			if (popul[a] == popul[b]) popul[a] = popul[b] = 0;
			else {
				if (popul[a] < popul[b]) swap(a, b);
				popul[a] -= popul[b];
				popul[b] = 0;
				uf[b] = a;
			}
		}
	}

	vector<int> ans;
	for (int i = 1; i <= N; i++) {
		if (popul[i]) ans.push_back(popul[i]);
	}

	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (auto a : ans) cout << a << ' ';
}