[백준/BOJ] 백준 1396번 : 크루스칼의 공

https://www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 연결하는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 www.acmicpc.net 문제에 대한 접근은, 간선을 가중치 순으로 정렬하고 각 쿼리에 대해 어떠한 간선까지 합쳤을 때, 쿼리의 출발지에서 목적지까지 가는지 이분 탐색을 통해 구할 수 있다. 출발지에서 목적지까지 갈 수 있는지 여부는, 유니온 파인드에서 출발지와 목적지가 같은 그룹이 되는지 확인하는 방법을 이용했다. 하지만 쿼리가 많아, 각 쿼리마다 하나씩 진행하지 않고 병렬 이분 탐색을 이용해서 문제를 ..

2023.10.19