백준 1717번 집합의 표현 / C++ / 유니온 파인드(Union-Find)

알고리즘 개념: 유니온-파인드

유니온 파인드에 대해 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.

[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법

[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법

 

백준 1717번 집합의 표현

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

예제 보려면 더보기 클릭

예제 입력 1

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1

NO
NO
YES

---

문제를 정리하자면 3개의 숫자가 주어질 때 

0 a b는 a와 b를 합친다 -> Union

1 a b는 a와 b가 같은 집합인지 확인한다 -> Find 

로 나타낼 수 있다. 

Union과 Find를 구현한 함수는 Union-Find 개념에 설명이 올라와 있다. 

Find 연산 구현

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

Union 연산 구현

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return;
    else p[b] = a;
 }

 

 

---

제출한 코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define INF 1000005
using namespace std;
using ll = long long int;
int p[INF] = { 0 };
int n, m;
void fillp(int n) {
	for (int i = 0; i <= n; i++) p[i] = i;
}
int find(int n) {
	if (p[n] == n) return n;
	else return p[n] = find(p[n]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	else p[b] = a;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	fillp(n);
	int k, a, b;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		cin >> k >> a >> b;
		if (k == 1) {
			if (find(a) == find(b)) {
				cout << "YES" << "\n";
			}
			else
				cout << "NO" << "\n";
		}
		else
			merge(a, b);
	}


}