백준 1717번: 집합의 표현(C++)

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

1717번: 집합의 표현

 

전형적인 Union-Find 문제이다. 또는 분리 집합 유형이라고 불린다.

 

n이 포함된 집합을 나타내는 정수 배열로 r[n]을 사용하자.

 

먼저 0부터 n까지, r[n]을 자기 자신으로 초기화한다.

 

그리고 주어지는 명령에 따라서 union과 find를 구현한다.

 

0, a, b가 주어지면 a가 속한 곳을 b가 속한 곳으로 수정해준다.

 

가령, a가 속한 집합이 3이고, 3이 속한 집합이 2라면 r[3]이 b가 속한 집합으로 수정되어야 하기 때문에,

r[getParent(a)] = getParent(b) 의 로직을 사용한다.

 

getParent의 경우, r[n]=n이 나올 때까지, 즉 최상단 부모노드일 때까지 getParent가 실행되어야 한다.

 

#include<iostream>
using namespace std;

int r[1000001];
int n, m;

int getParent(int num) { //find
	if (r[num] == num)
		return num;
	else{
		return r[num] = getParent(r[num]);
	}
}

void join(int a, int b) { // union
	//a의 부모를 b의 부모로 수정
	r[getParent(a)] = getParent(b);



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i <= n; i++) {
		r[i] = i;
	}

	while (m--) {
		int cmd, a, b;
		cin >> cmd >> a >> b;

		if (cmd == 0) {
			join(a, b);
		}
		else {
			if (getParent(a) == getParent(b))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}

	return 0;
}