[BOJ] 18116 - 로봇 조립

1. 문제 해석

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

18116번: 로봇 조립

• 1부터 10^6까지 정수로 표현된 로봇의 부품이 있다. 부품 i가 속한 로봇은 robot(i)라고 표현한다.
• 서로 다른 로봇은 같은 부품을 가지지 않는다.
• 두 가지의 명령이 있다.
  • 서로 다른 부품 2개를 말해주면  두 부품은 같은 로봇의 부품을 의미한다.
  • 부품 번호 i를 말해주면 지금 까지 모은 robot(i)의 개수를 알려줘야 한다. 

2. 접근방법

• Union-Find(Disjoint set)을 이용하여 서로 다른 부품을 하나의 군집으로 만들어 준다.
• 군집끼리 병합할 때 군집의 크기도 함께 병합한다.

 

3. 주의할 점

• 입력 N의 명령의 개수이지 부품의 개수가 아니다.

 

4. 소스코드

#include <iostream>

using namespace std;

char c;
int N, x, y;
int p[1000001];
int cnt[1000001];

int find(int x) {
	if (x == p[x]) return p[x];
	return p[x] = find(p[x]);
}

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

	for (int i = 0; i < 1000001; i++) {
		p[i] = i;
		cnt[i] = 1;
	}

	cin >> N;
	
	while (N--) {
		cin >> c;
		if (c == 'I') {
			cin >> x >> y;
			int px = find(x);
			int py = find(y);
			if (px != py) {
				p[px] = py;
				cnt[py] += cnt[px];
				cnt[px] = 0;
			}
		}
		else {
			cin >> x;
			cout << cnt[find(x)] << '\n';
		}
	}

	return 0;
}