Union-Find. [1717]

[1. 문제 설명]

초기에 0~n 이 각각의 집합을 이루고 있다.

합집한 연산과 두 원소가 같은 집합에 포함되어있는지 확인하는 연산을 수행

 

같은 집합에 포함되어있는 연산이 있을 때,

YES 또는 NO 를 출력

 

 

[2. 풀이 접근]

union find 이론 설명 링크로 대체

 

== union 시 주의 할 점

u 가 속한 집합, u 의 root 를 v 의 root 로 재설정해야 한다.

(u 가 속한 집합이 v 가 속한 집합의 높이보다 항상 작도록 만드는 경우)

 

이후, find 시 parents 배열은 알아서 재조정된다.

 

 

[3. 코드]