1647 백준 - 도시 분할 계획, C++, 크루스칼 알고리즘

1647번: 도시 분할 계획

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

int n, m, ans;
int parent[100001];
vector<pair<int, pair<int, int> > > edge;


int FindParent(int x){
    if(x == parent[x])
        return x;
    else 
        return parent[x] = FindParent(parent[x]);
}

bool IsSameParent(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return true;
    else 
        return false;
}

void Union(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    parent[y] = x;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int start, end, cost;
        cin >> start >> end >> cost;

        edge.push_back(make_pair(cost, make_pair(start, end)));
    }

    sort(edge.begin(), edge.end());
    for(int i = 0; i <= n; i++)
        parent[i] = i;
    
    for(int i = 0; i < edge.size(); i++){
        if(!IsSameParent(edge[i].second.first, edge[i].second.second)){
            Union(edge[i].second.first, edge[i].second.second);
            n--;
            if(n > 1)
                ans += edge[i].first;
        }
    }

    cout << ans << '\n';

}

---

 기존 MST를 만드는것과는 다르게 MST가 2개 나와야 한다는 것인데 (마을 2개로 분리한다고 했음) 이때 그냥 

    1. MST를 하나 만듬

    2. 위 MST에서 가장 비용이 큰 간선 제거

과정을 통해 마을 2개로 만들 수 있었다. (아마 마을 1개당 집 2개 이상 조건이 있다면 어려웠을 것 같다). 그리고 생각보다 입력 시간이 길어 fast io 코드를 넣거나 scanf, printf를 사용해야 시간이 빠르게 나오는 문제였다