[코드트리] 최소 스패닝 트리 분할 C++

문제

https://www.codetree.ai/missions/9/problems/minimum-spanning-tree-split?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

크루스칼 알고리즘(정렬 후 가중치가 작은 것 순서대로 간선을 연결)을 이용해 MST(최소 스패닝 트리)를 만든다.

간선을 연결하면서 가중치가 가장 큰 것을 저장하고(연결된 간선 중 가장 큰 것), 가중치 합에서 뺀다.

하나의 간선을 제거함으로써 2개의 연결 그래프로 분할된다. 

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

using namespace std;

const int MAX_N = 10'000;

int n, m;
int uf[MAX_N+1];
vector<tuple<int,int,int> > edges;

int myFind(int x){
    if(uf[x]==x) return x;
    return uf[x]=myFind(uf[x]);
}
void myUnion(int x, int y){
    x=myFind(x), y=myFind(y);
    if(x==y) return;
    uf[x]=y;
}


int main() {
    cin >> n >> m;
    for(int i=1; i<=n; ++i){
        uf[i]=i;
    }
    for(int i=1; i<=m; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        edges.push_back({w, a, b});
    }

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

    int weightSum = 0, maxWeight=0;
    for(auto e : edges){
        int w, a, b;
        tie(w, a, b) = e;
        if(myFind(a)==myFind(b)) continue;
        myUnion(a, b);
        weightSum+=w;
        maxWeight=max(maxWeight, w);
    }

    cout << weightSum-maxWeight << '\n';
    return 0;
}