[일반] 유니온파인드구현할때, rank랑 경로압축 둘다 해줘야댐?

[ㅇㄴ(220.84)]

귀찮은데 경로압축만 하면 효율 쓰레긴가

[즈우북(121.161)]

대부분의 경우 경로압축만 하면 되고 둘 다 하면 더 느려짐 union find한 거 되돌려야한다거나 하는 특수한 알고리즘 쓸때(offline dynamic connectivity같은거)나 rank 압축하고 그 외엔 그냥 path 압축만

[익명(121.125)]

이론상으로는 둘다해야 시복이 보장되는데 practical하게는 경로압축만 하는게 나음

[옥토끼(moonrabbit2)]

둘중 하나만 해도 O(logN) 보장임

[익명(39.7)]

말이 다달러 ㅅㅂ ㅋㅋㅋ