재원블로그 재원블로그

유니온 파인드는 집합간의 합집합을 나타낼 때 사용하는 자료구조이다. A[] = { 0, 1, 2 }, B[] = { 1, 2, 3 } 이라고 하고, B 배열이 A 배열로 합쳐진다고 가정하면 union 연산을 수행한 후에는 A[] = { 0, 1, 2, 3 } 이 되는 것이다. 유니온 파인드에서는 두 가지의 연산을 수행할 수 있는데, 한 집합의 대표를 리턴하는 find 와 두 집합을 합치는 union 연산이 있다. 초기 상태에는 한 원소가 하나의 집합이 되고, 그 원소가 그 집합의 대표가 된다. C++로 구현한 기본적인 유니온 파인드는 다음과 같다. vector parent; void init(vector p) { for (int i = 0; i < parent.size(); i++) { parent[i]..