[백준] 21924번 - 도시 건설 (C++) 문제 및 풀이

초코칩프라푸치노 2022. 1. 18. 17:13

문제) 백준 - 최소 스패닝 트리 - 도시 건설

https://www.acmicpc.net/problem/21924

21924번: 도시 건설

첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두

www.acmicpc.net

전형적인 최소 스패닝 트리 문제입니다. rank를 이용한 Disjointset과 kruskal 알고리즘을 이용하여 최소 비용을 구합니다. 비용의 개수로 모든 도시 연결 여부를 판단하여 -1 또는 절약 예산을 구합니다.

C++ 소스 코드)

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2020000~/21924_%EB%8F%84%EC%8B%9C%20%EA%B1%B4%EC%84%A4.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions

BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHub.

github.com

PS) OverFlow를 조심합시다...

저작자표시 비영리 변경금지 (새창열림)