백준 1717 집합의표현 c++ // 유니온 파인드 구현방법

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

1717번: 집합의 표현

1. 의사코드

*파인드 : 

자기자신이 부모임 == 루트노드

아님 : 부모의 조상을 찾아서 리턴

 

*유니언 : 

조상이다를때, 작은쪽으로 합침

rootA의 부모 = rootB // parent[rootA]=rootB

※ A의 부모 = rootB 가 아님에 주의! // parent[A]=rootB (X)

#include <bits/stdc++.h>
using namespace std;

int n, m;
int parent[1000000 + 1]; //a[i]:3 i의 소속은 3이다.

//node의 조상찾기
int find(int node) {
	if (parent[node] == node) return node;
	return parent[node] = find(parent[node]);
}
void union_(int a, int b) {
	int rootA = find(a);
	int rootB = find(b);

	if (rootA == rootB) return;
	if (rootA < rootB) {
		parent[rootB] = rootA;
	}
	else
		parent[rootA] = rootB;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i <= n; ++i) {
		parent[i] = i;
	}
	for (int i = 0; i < m; ++i) {
		int op, a, b;
		cin >> op >> a >> b;
		if (op == 0) {
			union_(a, b);
		}
		else {
			if (find(a)==find(b)) cout << "YES\n";
			else cout << "NO\n";
		}
	}


	
	return 0;
}