[BOJ] 백준 15809 전국시대

백준 15809 전국시대

문제 링크 : https://www.acmicpc.net/problem/15809

이 문제는 Union - Find 유형입니다.

같은 집합에 속한 노드끼리는 같은 국가로, 그 외는 다른 국가로 인식하여

정복 및 대결 하는 문제 였습니다.

Find 함수는 어떤 노드를 입력 받았을 때, 그 노드가 속한 노드를 반환합니다.

Union 함수는 두 노드를 입력받고, 루트노드가 다르다면 병합 합니다.

Battle 함수는 두 노드를 입력받되, 루트노드가 같다면 둘다 멸망, 다르다면 정복 합니다.

소스코드 : 

#include 
#include 
#include 
using namespace std;

vector v(100001);
vector vsize(100001, 1);

// Find 함수로, 각 번호의 루트가 되는 번호를 찾는다.
int Find(int node) {
 if (node == v[node]) {
  return node;
 }
 return v[node] = Find(v[node]);
}
// 루트로 찾은 숫자를 비교하여 다르다면 병합을 실시한다.
void Union(int a, int b) {
 int node1 = Find(a);
 int node2 = Find(b);
 if (node1 != node2) {
  if (vsize[node1] > vsize[node2]) swap(node1, node2);
  vsize[node2] = vsize[node2] + vsize[node1];
  vsize[node1] = 0;
  v[node1] = node2;
 }
}
// 루트가 다르다면 배틀을, 같다면 멸망 시킨다.
void Battle(int a, int b) {
 int node1 = Find(a);
 int node2 = Find(b);
 if (node1 != node2) {
  if (vsize[node1] == vsize[node2]) {
   vsize[node1] = 0;
   vsize[node2] = 0;
   v[node1] = 0;
   v[node2] = 0; 
   return;
  }
  else if (vsize[node1] > vsize[node2]) swap(node1, node2);
  
  vsize[node2] = vsize[node2] - vsize[node1];
  vsize[node1] = 0;
  v[node1] = node2;
 }
}
int main() {
 int N, M;
 cin >> N >> M;
 for (int i = 1; i <= N; i++) {
  v[i] = i;
 }
 for (int i = 1; i <= N; i++) {
  cin >> vsize[i];
 }
 for (int i = 1; i <= M; i++) {
  int O, P, Q;
  cin >> O >> P >> Q;
  if (O == 1) {
   Union(P, Q);
  }
  else {
   Battle(P, Q);
  }
 }
 int nation = 0;
 // size가 1 이상이면 독립된 국가로 인정한다.
 for (int i = 1; i <= N; i++) {
  if (vsize[i] >= 1) {
   nation++;
  }
 }
 cout << nation << endl;
 // 정렬하여 오름차순.
 sort ( vsize.begin(), vsize.end());
 for (int i = 100000 - nation+1; i <= 100000; i++) {
  cout << vsize[i] << ' ';
 }
}