https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이과정 크루스칼 알고리즘의 대표적인 문제다. 두 개의 마을로 나눠야 하니까 마지막 간선(가장 가중치가 큰 간선) 을 안 더해주면 된다. #include #include #include using namespace std; int N, M, A, B, C; int parent[100001]; vector v; int getParent(int x) { if (x..

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 풀이과정 크루스칼 알고리즘의 대표적인 문제이다. 연결된 노드의 개수가 정점의 개수 -1개가 되면 노드 연결을 끝내고, 가중치의 합을 출력하면 된다. #include #include #include using namespace std; int V, E, A, B, C; int parent[10001]; vector graph; int getParent(..