[Gold / 1717] 집합의 표현

문제 링크

---

🔷 분류

자료 구조, 분리 집합

✒️ 문제 설명

초기에 $n+1$개의 집합 $\{0\},\{1\},\{2\},\dots ,\{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

⬅️ 입력

첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

➡️ 출력

1로 시작하는 입력에 대해서 $a$와 $b$가 같은 집합에 포함되어 있으면 “YES” 또는 “yes“를, 그렇지 않다면 “NO” 또는 “no“를 한 줄에 하나씩 출력한다.

💻 코드 (C++)

#include <iostream>
using namespace std;

int p[1000001]; // 부모 저장 배열

int find(int a) {
	if(a == p[a]) return a;
	else return(find(p[a])); // 재귀함수
}

void uni(int a, int b) { // 부모끼리 연결
	a = find(a);
	b = find(b);	

	if(a != b) p[b] = a;
}

bool check(int a, int b) {
	a = find(a);
	b = find(b);
	if(a == b) return true;
	else return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
    
    for(int i = 0; i <= n; i++) p[i] = i;
    
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if(a == 0) {
			uni(b, c);
		} else {
			if(check(b, c)) cout << "yes\n";
			else cout << "no\n";
		}
	}
	return 0;
}