모든 친구와의 관계가 사향트리꼴로 연결된 경우

1 2

2 3

3 4

...

n-1 n

n n+1

총 n+1 명의 친구가 있겠죠?

그리고 이경우엔 최악의 경우 질문자님이 작성하신 코드로는 O(N^2)의 시간이 소요됩니다.

왜냐하면 

1에 2를 붙이고, 그 2을 3에 붙이고, 그 3을 4에 붙이고, 그 4를 5에 붙이고... 하면 union을 실행시킬때 마다 탐색수가 1씩 늘어나면서, 2+3+4+5+6+7+...+n+1

가 되서 O(N^2)이 됩니다.

그리고 주어진 n은 100,000 이므로 시간초과가 날 수 밖에 없습니다.

randomize algorithm으로 푸시거나, 다른 휴리스틱을 사용하여 최적화 시키는 방법이 있겠지요

수정합니다.

1에 2를 붙이고 => 1을 2에 붙이고

map<string, int> m 도 pointer로 돌려보세요. 

m 사이즈가 너무 커서 TLE가 난 모양입니다.

윗분의 댓글은 무시하셔도 좋습니다. 정석대로 잘 짜셨어요.

여담이지만..shjgkwo님, find 함수에서 "return p[x] = find(p[x]);" 이 부분때문에 말씀하신 TLE가 나는 경우는 생기지 않게 됩니다.

답변 감사합니다!  @shjgkwo 님께서 말씀 하신 것은 pichulia님 말대로 

return p[x] = find(p[x]);로 경로압축을 해주었습니다.

randomize algorithm나 휴리스틱은 전혀 몰랐던 알고리즘인데 그 방법으로도 풀어봐야겠네요!

감사합니다!

@pichulia

말씀해주신대로 map<string,int>도 포인터나 참조로 바꿨더니 바로 해결 되었습니다!

감사합니다!

아.. 뭔생각으로 쓴글인지 ㅠㅠ

질문자님 죄송합니다. O(n log n) 이네요..

2^k 꼴로 구성해서 노드를 붙이는 방식으로 하면 그게 최악인데 말이죠...

아 진짜 뭔생각으로 저렇게 썼지 ㅠㅠ

지적해주신 @pichulia 님 감사합니다 :)

random 으로 union 구성하라는 말은 무시하셔도 좋아요..

rank hueristic 이라고 path compression 과 섞어 쓰면 엄청 빨라지는 게 있는데 이것도 찾아보세요!