cjswodmlskfk   4년 전

아래는 되는 소스입니다. 그런데

void union_find(int a, int b) {
int root_a = find(a);
int root_b = find(b);
// 주석에 적은 대로 작성을 하면 틀리게 됩니다.
if (root_a < root_b) {
//parents[b] = root_a;
parents[root_b] = root_a;
} else {
//parents[a] = root_b;
parents[root_a] = root_b;
}
}\

union_find 부분에서

parents[root_b]를 parents[b] 로 바꾸면 틀리게 됩니다.

저는 find 함수에서 갱신이 다 될 것이라고 생각했는데 아니었습니다. 

혹시 안 되는 직관적인 이유를 알려주실 수 있으신가요? 감사합니다. 

Green55   4년 전

A : 1

B : 2 <- 3

인 상황에서

merge(1,3)을 하면 잘못된 코드로는

A : 1 <- 3

B : 2

가 됩니다.

A : 1 <- 2<- 3

이 되어야 맞습니다.

cjswodmlskfk   4년 전

감사합니다. find() 한 것과 상관없이 나의 최종 부모가 아니라 그냥 받은 값들을 잇고 끝나는군요.

댓글을 작성하려면 로그인해야 합니다.