[골4] 1197 - 최소 스패닝 트리

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

using namespace std;

class Edge
{
public:
	int node[2];
	int dist;

	Edge(int a, int b, int dist)
	{
		node[0] = a;
		node[1] = b;
		this->dist = dist;
	}

	bool operator<(Edge& edge) { return dist < edge.dist; }
};

int parents[10001];

int GetParent(int* parent, int x)
{
	if (parent[x] == x)
		return x;

	else
		return parent[x] = GetParent(parent, parent[x]);
}

int Union(int* parent, int a, int b)
{
	a = GetParent(parent, a); b = GetParent(parent, b);

	if (a < b)
		return parent[b] = a;

	else
		return parent[a] = b;
}

int Find(int* parent, int a, int b)
{
	a = GetParent(parent, a); b = GetParent(parent, b);
	return a == b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int vertex, edge; cin >> vertex >> edge;
	
	for (int i = 0; i < vertex; i++)
		parents[i] = i;

	vector<Edge> v;

	for (int i = 0; i < edge; i++)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		v.push_back(Edge(from, to, cost));
	}
	sort(v.begin(), v.end());
	int sum = 0;

	for (int i = 0; i < v.size(); i++)
	{
		int a = v[i].node[0] - 1, b = v[i].node[1] - 1;

		// 사이클이 발생하지 않는 경우 
		if (!Find(parents, a, b))
		{
			sum += v[i].dist;
			Union(parents, a, b);
		}
	}
	cout << sum;
}