KOITP 동맹의 동맹은 동맹

 

 

 

이 문제는 Union & Find 문제이다.

 

공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진
원소들에 대한 정보를 저장하고 조작하는 자료구조

 

초기화에는 자신이 부모인 것으로 초기화 해준다.

 

그리고 나서 부모 - 자식 관계

즉, 문제에서 동맹관계를 알려주면

 

해당 부모 자식관계를 par[] 배열에 맺어준다

 그런데 어차피

동맹의 동맹은 동맹이므로

 

최종적으로 가장 높은 root를 같은걸 가리키고 있으면

같은 동맹이란 사실을 알 수 있다.

 

그래서 find 펑션에서

가장 높은 root를 찾을 수있도록 재귀로 구현해주었다.

 

 

 

 

 

 

 

동맹관계를 맺어주는

type =0 이면

각각 부모 - 자식관계를 맺어주고

 

type =1 이면 가장 높은 root를 구해주는

find 펑션을 통해

그 값이 같은지 비교해서

 

출력해준다.