[골4] 1922 - 네트워크 연결

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

using namespace std;

#define MAX 100001

struct sEdge
{
    int val, a, b;
};

vector<sEdge> graph;
int parent[MAX];
int res = 0;

int Find(int x)
{
    return (parent[x] == x) ? x : parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
    x = Find(x), y = Find(y);

    if (x != y)
        parent[y] = x;
}

bool Cmp(sEdge edge1, sEdge edge2)
{
    return (edge1.val < edge2.val);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int computers, cables; cin >> computers >> cables;

    for (int i = 1; i < MAX; i++)
        parent[i] = i;

    for (int i = 0; i < cables; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph.push_back({ c,a,b });
    }
    sort(graph.begin(), graph.end(), Cmp);

    for (int i = 0; i < cables; i++)
    {
        auto a = graph[i].a, b = graph[i].b;

        if (Find(a) != Find(b))
        {
            Union(a, b);
            res += graph[i].val;
        }
    }
    cout << res;
    return 0;
}