문제 아이디어

친구가 되는 요소들이 정수가 아니라 Fred, Barney 등의 string으로 주어주기 때문에, 이름별로 인덱스를 주어 해싱을 하면 편하게 풀 수 있을 것이다.
모든 친구들의 관계를 맺고 갯수를 구하는 것이 아니라, 관계를 맺을 때마다 관계에 포함된 친구들의 갯수를 구해야한다. 친구 관계의 수 F는 최대 100,000이므로 반복문을 2번 돌리는 순간 O(F^2)로 시간초과가 날 수 있음을 알 수 있다.
시간초과를 해결하기 위해서는 네트워크에서 대표가 되는 사람이 네트워크에 포함된 사람들의 인원수를 가지고 있어야하며, 새로 추가될 때마다 갱신해줘야 한다.
관계를 맺을 때마다 DFS/BFS로 문제를 푼다면 시간초과가 날 것이고 (위에서 언급), 그렇다면 어떠한 알고리즘으로 시간초과를 해결할지 생각해봐야 한다.
그룹의 갯수를 찾거나, 동일한 그룸에 포함되어 있는지 확인하는 등을 요구하는 문제는 Union Find를 활용해서 푸는 문제들이 많을 것이다! 우리는 이 문제를 Union Find로 해결해 보도록 하겠다.
- Union Find가 익숙하지 않으신 분은 그전 MST포스팅을 보고 오시면 됩니다.

문제 풀이

받은 이름과 이름에 맞는 인덱스를 매핑해주는 map<string, int> nameMap 을 사용할 것이다.
- 문제 첫번째 예시로, Fred = 0, Barney = 1, Betty = 2, Wilma = 3 을 갖게 될 것이다.
Union Find를 통해 같은 네트워크에 속해있는지 알기 위해 필요한 것으로 map<int, int> pMap 을 사용할 것이다.
- 초기값은 0 = 0, 1 = 1, 2 = 2, 3 = 3 을 갖게 될 것이다. (즉, 자기 자신이 최상위 부모라는 뜻이다.)
네트워크에 속해있는 최상위 부모가 총 노드갯수를 가지기 위해 필요한 map<int, int> countMap 을 사용할 것이다.
- 매번 Union Find를 하여, 최상위 부모를 바꿔줄 때마다 기존의 최상위 부모가 가지고 있는 친구들의 수를 새로 부모가 될 최상위 부모의 countMap에 더해준다.

C++ 의 경우에는 자료형을 지정해주므로 처음 갱신해줄 때 1번과 같이 써도 상관없지만, 후에 있을 오류를 방지하기 위해서는 2번과 같이 쓰는 것이 좋다.

Python을 써봤던 사람이라면, a, b, c = tuple(1, 2, 3) 의 간결함이 그리울 것이다. 그리워하지 말라! C++에도 Python만큼 사기는 아니지만, 비슷한 기능이 있으니!