[백준] 1922. 네트워크 연결 (C++)

1922번: 네트워크 연결

문제 설명

1. 모든 컴퓨터를 연결하는 데 드는 최소 비용 출력

 

풀이

크루스칼 알고리즘 : '모든' 컴퓨터를 연결하는데 드는 '최소' 비용

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;

class Edge {
public:
    int node[2];
    int dis;
    Edge(int a, int b, int c) {
        this->node[0] = a;
        this->node[1] = b;
        this->dis = c;
    }
    bool operator<(Edge &edge) {
        return this->dis < edge.dis;
    }
};

class UNION_FIND {
public:
    vector<int> parent, length;
    UNION_FIND() {
        parent.resize(n+1);
        length.resize(n+1, 1);
        for(int i=1; i<=n; i++) parent[i] = i;
    }
    int find(int a) {
        if(parent[a] == a) return a;
        return find(parent[a]);
    }
    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b) return;
        if(length[a] < length[b]) swap(a, b);
        parent[b] = a;
        length[a] += length[b];
        length[b] = 0;
    }
};

int main() {
    cin >> n >> m;
    vector<Edge> edges;
    UNION_FIND uf;
    int ans = 0;
    for(int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back(Edge(a, b, c));
    }
    sort(edges.begin(), edges.end());
    for(int i=0; i<m; i++) {
        if(uf.find(edges[i].node[0]) == uf.find(edges[i].node[1])) continue;
        uf.merge(edges[i].node[0], edges[i].node[1]);
        ans += edges[i].dis;
    }
    cout << ans << '\n';
    return 0;
}