백준 1396번 (병렬 이분 탐색/PBS), 크루스칼의 공
문제 BOJ 1396번 풀이 쿼리가 하나 있다고 가정하면 아래와 같이 풀 수 있습니다. * mid보다 작거나 같은 간선들만 합쳐줍니다. (Union Find) * (쿼리) 정점 u와 v의 루트 노드가 같으면, right를 mid로 두고 그렇지 않으면 left를 mid + 1로 만들어준 뒤 계속 이분 탐색을 돌립니다. - 가중치(고유값)이 mid 이하인 간선을 이용해 정점 u, v를 포함하는 MST를 구성할 수 있냐 는 결정 문제로 볼 수 있습니다. 위와 같은 이분 탐색을 사용하면 간선을 이분 탐색하는데 $ O(log M) $, mid보다 작거나 같은 간선을 합치는데(MST를 만드는데) 시간이 $ O(M logN) $ 이고, 쿼리가 총 $ Q $개 있으니 총 시간 복잡도는 $ O (QM log N log ..
2020.10.03