백준 1922번 네트워크 연결 C++

출처 : https://www.acmicpc.net/problem/1922

 

기본적인 최소 스패닝 트리 문제인 것 같다. 유니온 파인드를 이용해서 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

struct Computer {
    int a;
    int b;
    int cost;
    bool operator<(const Computer& other)const {
        return cost < other.cost;
    }
};

vector<int> parent;
vector<int> height;

int GetParnet(int n) {
    if (n == parent[n])
        return n;
    return parent[n] = GetParnet(parent[n]);
}

void Merge(int u, int v) {
    u = GetParnet(u);
    v = GetParnet(v);

    if (u == v) return;

    if (height[u] > height[v])
        ::swap(u, v);

    parent[u] = v;

    if (height[u] == height[v])
        height[v]++;
}

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

    cin >> n >> m;

    parent = vector<int>(n + 1);
    height = vector<int>(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    int ans = 0;
    vector<Computer> computers;
    for (int i = 0; i < m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        computers.push_back({ a,b,cost });
    }

    sort(computers.begin(), computers.end());

    for (auto a : computers) {
        if (GetParnet(a.a) == GetParnet(a.b)) continue;
        Merge(a.a, a.b);
        ans += a.cost;
    }

    cout << ans;
}