백준 1647 C++

#define ll long long int

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

// 정점과 간선 정보를 담는 구조체 정의
struct graph {
	int a, b; // 간선의 양 끝점
	int w;    // 간선의 가중치

	// 우선순위 큐에서 사용하기 위한 비교 연산자 오버로딩
	bool operator<(const graph& item) const {
		if (w > item.w) {
			return true;
		}
		else return false;
	}
};

// 전역 변수 선언
int N, M;                  // 정점의 개수 N, 간선의 개수 M
int arr[100003];           // 사용되지 않는 배열
int parent[100003];        // 각 정점의 부모 정보를 저장하는 배열
priority_queue<struct graph> pq; // 간선의 가중치를 기준으로 최소 힙을 구성하는 우선순위 큐

// 정점 x의 부모를 찾는 함수
int getParent(int x) {
	if (x == parent[x]) return x;
	else return parent[x] = getParent(parent[x]);
}

// 두 정점을 합치는 함수
void setUnion(int a, int b) {
	int x = getParent(a);
	int y = getParent(b);
	if (x < y) {
		parent[y] = x;
	}
	else {
		parent[x] = y;
	}
	return;
}

// 두 정점이 같은 집합에 속해 있는지 확인하는 함수
bool isUnion(int a, int b) {
	if (getParent(a) == getParent(b)) return true;
	else return false;
}

int main()
{
	// 입출력 속도 향상을 위한 설정
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);

	// 정점의 개수 N과 간선의 개수 M 입력
	cin >> N >> M;

	// 간선 정보를 우선순위 큐에 저장
	for (int i = 0; i < M; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		struct graph item = { a, b, w };
		pq.push(item);
	}

	// 초기 상태에서 각 정점은 자신을 부모로 갖도록 초기화
	for (int i = 1; i <= N; i++) parent[i] = i;

	int cnt = 0;    // 선택된 간선의 가중치 합을 저장하는 변수
	int last_w = 0; // 마지막으로 선택된 간선의 가중치를 저장하는 변수

	// 최소 신장 트리 구성을 위한 Kruskal 알고리즘 수행
	while (!pq.empty()) {
		struct graph item = pq.top();
		pq.pop();

		// 두 정점이 같은 집합에 속해 있지 않다면 간선 선택
		if (!isUnion(item.a, item.b)) {
			cnt += item.w;
			last_w = item.w;
			setUnion(item.a, item.b);
		}
	}

	cout << cnt - last_w << "\n";

	return 0;
}