union-find

union and find는 여러 개의 원소가 존재하고 특정 원소가 어떤 집합에 속해있는지 확인할 때, 집합끼리 연결해줄 때 이용하는 자료구조이다. 

 

처음에 아무것도 연결이 안되어 있을 때

 

uf 배열은 부모노드의 번호를 가리키고 있다.

 

uf[1] = 3, uf[5] = 6 으로 해주었을 때

부모 노드가 바뀌게 된다.

 

만약 union(5,1)로 서로 자기 자신이 아닌 부모 노드가 존재할 때는 find 함수를 써야한다.

find 함수를 써서 uf[x] = x 인경우까지 찾아줘야 한다.

그리고 나온 값들로 union을 하게 된다.

find(5) => 6 -> find(6) => 6 이므로 멈춘다 , find(1) => 3 find(3) => 3 멈춘다 그리고 -> union(6,3) 을 하게 된다.

find(x) = x   

find(y) = y 이므로 uf[x] = y 해주게 되면 서로 연결이 된다.

 

그러나 이 방식은 시간이 걸리는 방식이다.

1, 2, 3, 4, 5, 6, ... n 개로 이루어진 노드들이 일자로 모두 연결되어 있다면 find시에 O(n) 이 걸릴 것이다. 그러면 너무 오래 걸리기 때문에 개선된 방식이 존재한다.

 

개선된 union - find는 uf[x] = x 를 찾으면 나머지 지나왔던 노드들을 모두 다 x를 향하게 바꿔주는 것이다. 그러면 다음에

동일 노드에 대하여 find 수행 시 빠르게 부모 노드를 찾을 수 있게 된다.

에서

 

이런 식으로 바뀌어서 find 연산 시 빠르게 찾을 수 있게 된다.