로구 P3366 【템플릿】최소 신장 트리
문제 링크
https://www.luogu.org/problemnew/show/P3366
문제 설명
주어진 무방향 그래프의 최소 신장 트리를 구하시오. 만약 그래프가 연결되지 않은 경우, "orz"를 출력하십시오.
입출력 형식
입력 형식:
첫 번째 줄에는 두 개의 정수 N, M이 포함되며, 이는 그래프에 총 N개의 정점과 M개의 무방향 간선이 있음을 나타냅니다. (N <= 5000, M <= 200000 ...
7월 17일 02:14에 게시됨
최소 신장 트리: 비음수 가중치 무방향 그래프
프림 알고리즘 (인접 행렬 기반)
다익스트라 알고리즘과 유사하지만, 거리 업데이트 대상이 다른 점이 핵심이다. 프림은 현재 신장 트리에 포함된 정점들과 연결된 간선 중 최소 가중치를 선택하여 확장한다.
크루스칼 알고리즘
Union-Find 자료구조를 활용하며, 모든 간선을 가중치 기준으로 오름차순 정렬한다. 두 정점이 이미 같은 연결 컴포넌트에 속해 있으면 간선 ...
7월 6일 19:29에 게시됨