문제 백준 14621번 풀이 빨간색 파란색을 잇는 간선을 제외하고 모두 제거합니다. 남은 간선을 가지고 정점을 모두 연결시킬 수 있는 MST (최소 스패닝 트리)를 만들면 됩니다. 정렬하는데 $ O(MlogM) $, 연결하는데도 $ O(MlogM) $이 걸리니 시간 복잡도 $O(MlogM)$에 해결할 수 있습니다. MST를 구하는 방법 (백준 1197번, 최소 스패닝 트리(MST)를 구하는 크루스칼 알고리즘) 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef ..

문제 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 ..

문제 백준 1197번 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 크루스칼 알고리즘 3 3 1 2 1 2 3 2 1 3 3 테스트 케이스의 내용을 시각화하면 아래와 같습니다. 트리 구조를 유지하되, 간선의 가중치를 최소화하려면 (1, 3)의 간선을 제거하면 됩니다. ​ 크루스칼 알고리즘은 최소 비용 신장 트리를 찾는 알고리즘입니다. 작동 방법을 설명하기 위해 아래 그래프의 최소 스패닝 트리를 구해보겠습니다. 우선, 간선의 가중치가 오름차순이 되도록 정렬을 ..