[일반] union-find 구현 질문

[익명(210.94)]

find 구현 코드에서 

int find(int x)

{

if (p[x] < 0) return x;

return p[x] = find(p[x]); << 이 부분

}

생각해보니까

return find(p[x]);

를 써도 되는데 어차피 find 함수가 x가 속한 집합의 제일 상단 노드가 일치하는지 알아보려고 찾는 거니까 

미리 p[x]에 업데이트 해둬서 다음 find때 찾는 시간 줄이려는 용도인가요?

[익명(118.235)]

path compression 하는거임 그거 없으면 tle남

[익명(210.94)]

안써도 되는게 아니고 무조건 써야되는 거네요. 감사합니다

[익명(223.118)]

일자로 하나씩 붙인다고 생각해보셈 find가 O(N) 되지

[익명(211.57)]

저거만 쓰면 평균 로그, 스몰투라지만 써도 로그 둘 다 쓰면 거의 o(1)에 돌아감이 보장됨

[익명(61.74)]

맞읍니다