[BOJ/Gold 4] 백준 17250 은하철도(C++)

문제 링크

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

17250번: 은하철도

 

문제

하나의 은하 안에는 여러 행성들이 존재한다. 문명의 기술 발전으로 은하 내의 모든 행성들은 서로 여행할 수 있게 되었다.

드디어 오늘, 80,000 광년 떨어진 다른 은하와 우리 은하를 연결하는 은하 철도가 개통된다.

은하 철도가 개통되면 더 많은 행성을 여행할 수 있다는 사실에 은하 내 모든 행성의 주민들은 들떠있는 분위기이다.

우주철도공사 G-Express는 앞으로의 은하 철도 계획을 발표하였다.

우주는 너무 넓기 때문에, G-Express사는 은하가 연결될 때마다 몇 개의 행성들이 서로 여행할 수 있게 되었는 지를 알려주고자 한다.

G-Express사 기술개발팀의 직원인 당신에게 이 프로그램의 업무 요청이 들어왔다. 각 은하들의 행성 수와 철도 계획이 주어지면 해당 철도를 이용할 수 있는 행성들의 수를 실시간으로 안내하는 프로그램을 만들자.

입력

첫 번째 줄에 은하의 수 N과 철도의 개수 M이 주어진다.

두 번째 줄부터 N개의 줄에 N개의 각 은하 내에 존재하는 행성들의 수가 1번 은하부터 차례대로 주어진다. (행성을 세는 단위는 조(1012) 단위이다.)

그리고 N+2 번째 줄부터 M개의 줄에 걸쳐 은하와 은하 사이를 잇는 철도가 주어진다. 같은 은하 사이에 여러 개의 철도가 건설될 수 있다.

입력되는 N은 2 ≤ N ≤ 100,000, M은 1 ≤ M ≤ 100,000이고, 각 은하의 행성 수는 100(조)개를 넘지 않으며 아무 행성도 없는 경우는 없다.

출력

철도가 연결될 때마다 해당 철도를 이용할 수 있는 행성들의 수를 한 줄씩 출력한다.

예제 입력 1

5 4
3
9
10
11
15
1 2
2 3
4 5
4 3

예제 출력 1

12
22
26
48

예제 입력 2

5 4
3
1
4
15
9
1 2
3 1
2 3
2 4

예제 출력 2

4
8
8
23

알고리즘 분류

• 유니온 파인드

풀이

은하와 은하 사이를 연결할 때 번호가 더 작은 은하에 행성의 개수를 몰아주고 행성의 개수를 return하였으며, 만약에 이미 Union되어 있어 Parent가 같은 은하라면 은하의 Parent의 행성의 개수를 출력하였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int Planet[MAX];
int Parent[MAX];

void Init() {
	for (int i = 0; i < MAX; i++) {
		Parent[i] = i;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

int Union_Group(int X, int Y) {
	int P_X = Find(X);
	int P_Y = Find(Y);
	if (P_X < P_Y) {
		Parent[P_Y] = P_X;
		Planet[P_X] += Planet[P_Y];
		Planet[P_Y] = 0;
		return Planet[P_X];
	}
	else {
		Parent[P_X] = P_Y;
		Planet[P_Y] += Planet[P_X];
		Planet[P_X] = 0;
		return Planet[P_Y];
	}
	return 0;
}

void Input() {
	Init();
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> Planet[i];
	}
}

void Find_Answer() {
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		if (Find(A) != Find(B)) {
			cout << Union_Group(A, B) << "\n";
		}
		else {
			cout << max(Planet[Find(A)], Planet[Find(B)]) << "\n";
		}
	}
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}