문제
https://www.acmicpc.net/problem/15809
문제해설
N개의 국가들이 존재하고 각 나라별 병력이 있다.
국가들 사이에는 동맹과 전쟁이 있는데
동맹은 두 국가의 병력이 합쳐지는 것이고
전쟁은 병력이 더 큰 나라가 작은 나라를 먹는것이다.
전쟁을 하면 이긴 나라는 진 나라의 병력 만큼을 뺀 병력을 갖게되고
진 나라는 병력이 0이 된다.
남아있는 국가의 수와
각 국가의 병력을 출력하면 된다.
문제풀이
출력하는 부분에서 set을 이용해서 해보려고 하다가 많이 틀렸던 문제이다.
set은 적절하지 않은게 남아있는 국가의 병력이 똑같은 경우가 있기 때문이다.
아무튼 문제 자체는 어렵지 않다.
동맹은 유니온해주며 한쪽을 0으로 만들어주고
전쟁은 병력이 큰쪽에서 작은쪽을 빼준 값을 저장하고
작은쪽은 0으로 만들어주면 된다.
출력은 병력이 0이 아니고 루트 노드인 것들만 저장해서
정렬시켜 출력해주었다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int parent[100001];
vector<int>arr(1);
int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
arr[y] += arr[x];
arr[x] = 0;
parent[x] = y;
}
void battle(int x, int y) {
x = find(x);
y = find(y);
if (arr[x] > arr[y])
swap(x, y);
arr[y] -= arr[x];
arr[x] = 0;
parent[x] = y;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin >> n >> m;
for (int i = 1; i < 100001; i++)
parent[i] = i;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
arr.push_back(x);
}
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
if (a == 2)
battle(b, c);
else
merge(b, c);
}
vector<int>res;
for (int i = 1; i <= n; i++) {
if (arr[find(i)] == 0 || i != parent[i]) continue;
res.push_back(arr[find(i)]);
}
sort(res.begin(), res.end());
cout << res.size() << "\n";
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
return 0;
}