sksdong1   2달 전

dfs로 돌리면 맞는데

disjointset을 쓰니까 틀리는데 어떤 경우에 틀리는 걸까요?

겹치는 부분은 모두 한 그룹으로 묶는 다는 개념인데 왜 틀리는지 잘 모르겠네용

ljh6274   2달 전

53번째 줄을 for (int i = 0; i <= n; ++i) if (!c[find(i)]) c[find(i)]++, ret++; 로 변경해서 "맞았습니다!" 를  받았습니다.

위에서 merge 부분에서 각 그룹의 최상의 par만 바꿔주기 때문에 par[i]가 아니라 find(i)로 하는것이 맞는거 같네요 ~

sksdong1   2달 전

아 맞네요!
감사합니다~

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