lisagamer   2년 전

main 함수에서 부모가 서로 같은지 체크 하는 부분에서 아래 코드와 같이 

if (parent[a] == parent[b])
    cout << "YES" << '\n';

이렇게 하면 오답이 나고 

int aParent = findParent(a);
int bParent = findParent(b);
if (aParent == bParent)
    cout << "YES" << '\n';

이렇게 하면 정답이 되는데 왜 이런 차이가 발생하는지 모르겠습니다. unionParent 하면서 어차피 경로 압축이 일어났기 때문에 또 findParent를 할 필요가 없는 것이라 생각했는데 제가 놓치고 있는 것이 있을까요? 

circlezer0   2년 전

2,3을 합치고

1,2를 합친 상태에서 parent 배열의 값이

1,1,2이기 때문입니다.

findParent(3)을 해주어야 1,1,1으로 부모가 갱신됩니다.

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