[BOJ]4195번: 친구 네트워크

문제: https://www.acmicpc.net/problem/4195

---

유니온, 파인드 문제입니다.

 

주어지는 친구 관계가 최대 10만이고, 한 번 친구 관계를 조회할 때 최대 10만개까지 노드를 탐색할 수 있습니다. (BFS, DFS 기준)

그러므로 O(10만^2) 으로 시간초과가 납니다.

 

그래서 노드 탐색 시간을 log시간으로 줄여야 시간 초과를 해결할 수 있습니다.

노드 탐색 시간을 log 시간으로 내리는 방법은 친구 관계가 주어질 때 마다 유니온, 파인드를 사용하여 컴포넌트 간에 연결 관계를 맺어줍니다.

 

새로운 관계를 맺는다면 친구 관계는 component1 + component2의 합이 될 것이고

이미 맺어진 관계(같은 컴포넌트에 속함)라면 component1 이나 component2 중 하나의 값만 리턴하면 됩니다.

 

파인드의 시간 복잡도가 logN에 근사하므로 N^2을 NlogN으로 해결할 수 있습니다. 

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ4195.java