유니온 파인드

유니온-파인드(Union-Find)? Union-Find는 여러 개의 노드가 존재할 때, 어떤 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 방법 같은 그래프에 속하는지 어떻게 판별할까? 다음 그림을 보고 쉽게 이해하자 먼저 8개의 노드가 위와 같이 있다고 가정한다. 각 노드는 자기 자신을 가리키며 이는 자기 자신이 곧 루트 노드임을 의미한다. 여기서 5와 2가 연결되었다고 해보자. 그럼 다음과 같이 표현할 수 있다. 5번 노드에 2번 노드를 가리키는 값 2가 들어간다. 일반적으로 합칠 때는 더 작은쪽으로 합치며 이를 Union이라 한다. 그 다음 2와 1이 연결되었다고 해보자. 2번 노드는 1번 노드를 가리키며 이를 의미하는 값 1이 들어간다. 그럼 여기서 5번과 1번이 같은 그래프에 속하는..