[골4] 1647 - 도시 분할 계획

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

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

using namespace std;
using IntPair = pair<int, int>;
using NodePair = pair<IntPair, int>;

vector<NodePair> graph;
int parent[100001];

int Find(int x)
{
	if (parent[x] == x)
		return x;

	else
		return parent[x] = Find(parent[x]);
}

void Union(int a, int b)
{
	a = Find(a), b = Find(b);
	parent[a] = b;
}

bool IsCycle(int a, int b)
{
	return (Find(a) == Find(b));
}

int main()
{
	FAST_IO();

	vector<int> res;
	int n, m;
	cin >> n >> m;

	// 부모
	for (int i = 1; i <= n; i++)
		parent[i] = i;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graph.push_back({ {a, b}, c });
	}
	// 비용(거리값) 순으로 오름차순 정렬
	sort(graph.begin(), graph.end(), [&](NodePair a, NodePair b)
		{
			return a.second < b.second;
		});

	for (int i = 0; i < graph.size(); i++)
	{
		auto node = graph[i];
		int a = node.first.first;
		int b = node.first.second;
		int c = node.second;

		if (!IsCycle(a, b))
		{
			Union(a, b);
			res.push_back(c);
		}
	}
	int sum = 0;

	for (int i = 0; i < res.size() - 1; i++)
		sum += res[i];

	cout << sum;
	return 0;
}