[백준] 1197번 최소 스패닝 트리 (C++)

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

이번 문제는 크루스칼 알고리즘을 공부하면서 푼 문제이다.
크루스칼 알고리즘은 최소 스패닝 트리 즉, 스패닝 트리 중 가중치의 합이 최소인 트리를 구해주는 알고리즘이다.
따로 어려운 건 없었고, 크루스칼 알고리즘으로 풀면 답을 얻을 수 있다!

1. 간선 정보를 vector에 담고 가중치가 낮은 순으로 sort 해준다.
2. 부모의 정보를 담고 있는 parent 배열을 자기 자신으로 초기화 해준다.
3. 가중치가 낮은 순으로 간선 vector를 탐색한다. 이때, union-find를 이용해 정점의 부모가 같은지 확인한다.
   3-1. 부모가 같은 경우 싸이클이 생성되므로 넘어가준다.
   3-2. 부모가 다른 경우 누적 가중치 합 sum에 현재 간선의 가중치를 더해주고, parent를 병합해준다.

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

using namespace std;

int v, e;

struct edge {
public :
	int node[2];
	int dist;
	edge(int a, int b, int dist) {
		this->node[0] = a;
		this->node[1] = b;
		this->dist = dist;
	}

	bool operator <(edge& edge) {
		return this->dist < edge.dist;
	}
};

int get_parent(int* parent, int child) {
	if (parent[child] == child) return child;
	return get_parent(parent, parent[child]);
}

void union_parent(int* parent, int a, int b) {
	a = get_parent(parent, a);
	b = get_parent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

bool find(int* parent, int a, int b) {
	int l = get_parent(parent, a);
	int r = get_parent(parent, b);
	if (l == r) return true;
	else return false;
}

int main() {
	int a, b, c;
	cin >> v >> e;
	vector<edge> line;
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		line.push_back(edge(a, b, c));
	}
	sort(line.begin(), line.end());

	int *parent = new int[v];
	for (int i = 0; i < v; i++)
		parent[i] = i;
	int sum = 0;
	for (int i = 0; i < line.size(); i++) {
		if (!find(parent, line[i].node[0] - 1, line[i].node[1] - 1)) {
			sum += line[i].dist;
			union_parent(parent, line[i].node[0] - 1, line[i].node[1] - 1);
		}
	}
	cout << sum;
}