네트워크 연결

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int node, edge;
 
class Edge{
public:
    int node[2];
    int value;
    Edge(int a,int b, int v){
        this->node[0] = a;
        this->node[1] = b;
        this->value = v;
    }
    bool operator < (Edge & edge1){
        return this->value < edge1.value;
    }
};
vector<Edge> v;
int parent[10001];
 
int getParent(int * parent, int a){
    if(parent[a] == a){
        return a;
    }
    else 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);
 
    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));
    }
    for(int i = 0; i < node; i++){
        parent[i] = i;
    }
    sort(v.begin(), v.end());
    int sum = 0;
    for(int i = 0;i < v.size(); i++){
        if(findParent(parent, v[i].node[0]-1, v[i].node[1] -1) == 0){
 
            sum += v[i].value;
            unionParent(parent, v[i].node[0]-1, v[i].node[1] -1);
        }
    }
    cout<<sum<<'\n';
    return 0;
}

최소신장 트리 문제다.

Union으로 묶어주는것, 그리고 findParent해주면서 중복되지않게하는것

-> 최소신장트리 복습하면서 한번 더 풀어본 최소신장트리문제.