전체 소스를 본 것은 아니지만 저 부분이 어떻게 영향을 주는지만 설명을 드리겠습니다.  말씀드리는 예제가 정확히 작성하신 소스와 같지 않을 수 있지만

문제되는 부분은 설명이 될 것 같습니다.

a b

b c

c d

d e

e f

와 같은 네트워크가 주어졌을 때, 

* 수정 전의 경우

parent[b] = a 가 되고, parent[c] = b 와 같이 될 것이고.. 결국 parent[b~e] = a~d 로 차곡차곡 들어가겠죠.

마지막 e f 를 처리할 때 e의 find 는 d, c, b를 거쳐서 a라는 것이 나오게 될 것 같습니다.

* 수정 후의 경우는

find 에서 타고 들어가면서 가장 상위의 값으로 갱신을 하므로

parent[b~e] 는 전부 a 가 되므로 e f 처리시 find(e)는 바로 a를 줄 수 있습니다.

결국 수정 후와 같이 하면, parent 를 찾을 때 1,2번 안에 찾을 수 있기 때문에 100,000 정도 주어지면 수정전과 시간 차이가 많이 생길 수 있습니다.

Big O로 하면 수정 후는 O(N^2) 정도가 나올 것이고, 수정후는 O(N)정도 나올라나요?