Minimum spanning tree
-
(백준 6497번 전력난) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)PROGRAMMING/알고리즘 2024. 6. 17. 10:50
백준 6497번https://www.acmicpc.net/problem/6497 MST를 구해서 총 가중치의 합에서 빼면 되는 문제!MST를 구하기 위해서는 크루스칼 알고리즘을 사용하면 되는데, 크루스칼 알고리즘은 union find와 정렬을 잘 조합한 알고리즘이라서 어렵지 않다! #define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;int uf[200000];int find(int a) { if (uf[a] edges; edges.resize(n); int total = 0; for (int i = 0; i