Union find - 합집합을 찾는 대표적인 그래프 알고리즘이다. 합집합 여부를 판별할 수 있기 때문에 서로소 집합 여부도 판별할 수 있어 서로소 집합(Disjoint-set) 알고리즘이라고도 한다. Union find는 여러 개의 노드가 있을 때 두 노드를 선택해서, 현재 같은 그래프(집합)에 속하는지를 판별하는 알고리즘이다. 현재 같은 그래프에 속하는지 여부는 부모를 통해서 알 수 있는데 부모가 같다면 같은 그래프(집합)에 속한다고 볼 수 있는 것이다. 그럼 각 노드 별로 부모를 어떻게 설정하고 비교할 수 있는지 확인해보자. 먼저 아래와 같이 노드가 있다고 하자. 처음에는 모든 노드가 자기 자신을 부모로 설정한다. 그리고 다음과 같이 1과 2가 Union(합침)되면 2의 부모가 1로 변하게 된다. ..
