[일반] 유니온 파인드

[익명(221.154)]

유파 할때 union by rank 하는데 이것보다

int find(int n){

if(par[n]==n) return n;

return par[n]=find(par[n]);

}

해서 바로바로 올리는게 낫지 않음?

[익명(49.142)]

return par[n]=find(n); -> return par[n]=find(par[n]); 이렇게 수정해야 되지 않음?

[익명(221.154)]

ㅇㅇ 바로적어서 실수했네

[익명(49.142)]

나도 첨에 배울땐 랭크 썼는데 랭크 관리 귀찮기도하고 이렇게 해도 되길래 요즘엔 이렇게함

[익명(118.41)]

그거 다이나믹 최소 신장 트리 문제에서 그렇게 하면 시간초과남

[p플랫(urd05)]

그게 경로압축

[익명(58.77)]

union by rank랑 path compression 둘 중에 하나만 하면 Amortized log N이고 둘 다 하면 Amortized alpha N인데 둘 다 하면 상수 커서 둘 중 하나만 해도 충분함