집합 연산 Union-Find, 상향식 트리구조

Find - 어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별

Union - 서로 다른 두개의 집합을 하나의 집합으로 합병

=> 상향식 트리구조로 구현 하는 것이 효율적이다

상향식트리구조 : 위에서 아래로 내려오는 구조가 아닌 아래에서 위로 올라가는 구조

일반적으로 알고 있는 하향식 트리구조는 부모가 자식들만큼의 포인터 개수를 가지고 있어야 하지만

상향식은 자식이 부모를 가르키는 구조이므로 각 노드는 하나의 포인터만 가지고 있으면 된다

그러므로 어느 집합에 포함된 노드의 parent 를 계속 따라가다보면 최종 root 인 어느 집합인지를 알 수 있게 된다

(각 root 집합 명)