최소 스패닝 트리

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int parent[10001];
class Edge {
public:
    int node[2];
    long long value;
    Edge(int a, int b, int v) {
        this->node[0] = a;
        this->node[1] = b;
        this->value = v;
    }
    bool operator <(Edge& edge) {
        return this->value < edge.value;
    }
};
 
vector<Edge> v;
 
int getParent(int parent[], int a) {
    if (parent[a] == a) {
        return a;
    }
    return parent[a] = getParent(parent, parent[a]);
}
 
void unionParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
int findParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b) return 1;
    else return 0;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int node, edge;
    cin >> node >> edge;
    for (int i = 0; i < edge; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back(Edge(a, b, c));
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < node; i++) {
        parent[i] = i;
    }
    long long sum = 0;
    for (int i = 0; i < v.size(); i++) {
        if (!findParent(parent, v[i].node[0] - 1, v[i].node[1] - 1)) {
            sum += v[i].value;
            unionParent(parent, v[i].node[0] - 1, v[i].node[1] - 1);
        }
 
    }
    cout << sum << '\n';
    return 0;
}
 

다리만들기2 를 풀기전에 보아야하는 문제가아닐까싶다.

어려운 내용은아니다. findParent로 부모가 같은 노드가 아닐때, 연결해주고 연결함을 통해 가중치를 합해준뒤

노드를 하나하나 재귀로 부모를 같게 만들어 나가며 중복을 제거하는 방식이다.

유튜버 동빈나 https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

동빈나

님의 알고리즘 크루스칼 알고리즘을 보고 많이 배웠다.