유니온 파인드 최적화

여러 최적화 방법이 있겠지만 내가 배운 최적화 3가지 작성

 

1. find에서 수장 지정하면서 재귀

당연하게 사용하고 있는 방법

 

int find(int x) {
    return u[x]<0?x:u[x]=find(u[x]);
}

 

u[x] 에 내가 찾은 수장을 지정하면서 복귀한다.

 

 

2. 합치는 연산 uni 최적화

트리의 높이를 저장하는 rank 배열을 하나 더 만들고 트리가 낮은 집합을 큰 집합 아래로 가게 한다

만약 크기가 같다면 rank를 +1 한다

 

이러면 find 시에 최악에 O(n)을 피할 수 있음

 

if(rank[u] > rank[v]) swap(u, v);

parent[u] = v;

if (rank[u] == rank[v]) ++rank[v];

 

 

3. 집합의 크기를 음수로 저장하기

 

유니온파인드 

-1로 두고

 

수장은 음수 이면서 집합의 크기를 담기 위해

u[a]+=u[b] 로 해주고

부하들은 u[b]=a 로 양수로 표현해준다

 

그리고 find 할땐

int find(int x){return u[x]<0?x:u[x]=find(u[x]);}

 

로 음수면 수장이니 수장 번호 리턴

아니면 수장 찾아가기