[백준 1197번 C++] 최소 스패닝 트리
ㅂ크루스칼 알고리즘과 Union Find 알고리즘을 연습하기 좋은 문제다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘은 Greedy 알고리즘의 일종으로, 트리의 간선을 오름차순으로 정렬한 후 가중치가 가장 적은 간선부터 cycle이 생기기 전까지 차례로 합집합으로 만들어나가는 알고리즘이다. cycle의 생성 유무는 Union-Find 알고리즘으로 확인할 수 있다. 간선 정보를..
2022.07.21