[BOJ/C++] 1717 집합의 표현 : Union-Find

문제

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

풀이

Union-Find

• 집합을 관리하는 자료구조 "서로소 집합"

• 그래프에서 사이클 존재를 확인할 때 사용
  ex) MST 알고리즘 - 크루스칼

• 초기화 ⚠️범위 주의

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

• Find 함수

int Find(int node) {
	if (root[node] == node)
		return node;
	else
		return root[node] = Find(root[node]);
}

• Union 함수

void Union(int a, int b) {
	int parent_a = Find(a);
	int parent_b = Find(b);
	root[parent_b] = parent_a;
}

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> root;

int Find(int node) {
	if (root[node] == node)
		return node;
	else
		return root[node] = Find(root[node]);
}

void Union(int a, int b) {
	int parent_a = Find(a);
	int parent_b = Find(b);
	root[parent_b] = parent_a;
}


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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		root.push_back(i); // n=6이면 0 1 2 3 4 5 6 넣어야 함
	}

	int cmd, a, b;
	for (int i = 0; i < m; i++) {
		cin >> cmd >> a >> b;

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

	return 0;
}