백준1717 - 집합의 표현

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

1717번: 집합의 표현

Union-Find 알고리즘을 이용하여 풀었다. 공통조상을 찾는 알고리즘으로 부모 찾는 함수, 부모 병합하는 함수, 부모 같은지 확인하는 함수로 이루어진다.

 

처음에 모든 노드의 부모는 자기 자신으로 설정해야 한다. 그리고 부모를 병합하는 과정에서 작은 쪽의 부모를 큰 쪽의 부모로 설정한다.

 

문제에서는 0일 경우 부모를 합치고 1일 경우 부모가 같은지 확인하는 방식으로 진행한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 1000001
using namespace std;

int n, m;
int a, b, c; //a는 합집합을 만들지 공통 조상을 찾을지, b와 c는 합집합을 만드는
int set[MAX]; //공통 조상을 나타내는 곳

//부모 노드 찾기
int getParent(int set[], int x) {
	if (set[x] == x) return x;
	else return set[x] = getParent(set, set[x]);
}

//같은 부모인지 확인
bool findParent(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);

	//공통 부모이면 true, 다른 부모이면 false
	if (a == b) return true;
	else return false;
}

void unionParent(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);

	//작은 쪽으로 합치기
	if (a < b) set[b] = a;
	else set[b] = a;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		set[i] = i;
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (a == 0) { //0이면 
			unionParent(set, b, c); //합집합으로 만든다.
		}
		else { //1이면 
			if (findParent(set, b, c)) { //같은 집합에 있는지 확인해서 같은 집합이면
				cout << "YES" << '\n'; //YES출력
			}
			else { //같은 집합에 있는지 확인해서 다른 집합이면
				cout << "NO" << '\n'; //NO출력
			}
		}
	}
}