Union-Find. [4195]

[1. 문제 설명]

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

친구 관계가 생길 때 마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하도록 한다.

 

 

[2. 풀이 접근]

문제를 아래와 같이 변형 해볼 수 있다.

=> 친구 네트워크 == 두 정점이 연결 혹은 두 정점이 같은 집합

=> 두 개의 집합이 합쳐질 때마다,

=> 집합에 속한 원소의 개수를 출력하도록 한다.

 

즉, 두 노드(집합) 을 합칠 때 마다,

합쳐진 집합에 속한 원소 개수를 출력하면 된다.

 

union find 로 접근한다.

 

문자열 id 를 정수형 id 로 변환해야 한다.

map 을 사용할 경우 O(1) 에 정수형 id 를 얻을 수 있다.

 

union 시, 균형 잡힌 tree 를 만들기 위한 rank 배열 이외 에

집합의 개수를 저장할 size 배열도 추가로 생성한다.

 

== 실수한 점 ==

친구 관계 수 F 는 최대 10만개까지 주어진다.

한 줄 당 문자열 id 는 2개 이므로

문자열 id 는 최대 20만개 까지 주어진다.

 

따라서, union find 를 위한 각 배열의 최대 크기는 20만이 되어야 한다.

 

 

[3. 코드]