[백준] 15809 전국시대 c++

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

15809번: 전국시대

 

풀이과정

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

int N, M, op, P, Q;
int parent[100001], res[100001];

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

void unionParent(int op, int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a != b) { // 부모가 다르며 다른 집합일 경우
		if (res[a] < res[b]) swap(a, b); // 값 교환 함수
		parent[b] = a; // 작은 값의 부모 노드를 큰 값의 부모 노드에게
		if (op == 1) res[a] += res[b]; // 동맹
		else res[a] -= res[b]; // 전쟁
		res[b] = 0;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
		cin >> res[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> op >> P >> Q;
		unionParent(op, P, Q);
	}

	vector <int> v;
	for (int i = 1; i <= N; i++) {
		if (res[i] > 0) v.push_back(res[i]);
	}
	cout << v.size() << "\n";
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
}