1197번

1197번 - 최소 스패닝 트리

이전 문제에서 MST 를 multimap 을 이용해서 풀었고,

이번 문제에서는 MST 를 우선 순위 큐를 이용해서 문제를 풀었다.

우선 순위 큐는 큰 수 부터 나오기 때문에, -1을  곱해서 작은 수 부터 나오게 해서 정답을 구했다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
int p[10001];
int r[10001];
using namespace std;
 
int find(int x)
{
    if (p[x] == x)
    {
        return x;
    }
    else
    {
        return p[x] = find(p[x]);
    }
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return;
    }
 
    if (r[x] < r[y])
    {
        p[x] = y;
    }
    else if (r[x] == r[y])
    {
        p[y] = x;
        r[x]++;
    }
    else
    {
        p[y] = x;
    }
 
    return;
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
 
    priority_queue<pair<int,pair<int,int>>> q;
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q.push({ -c,{a,b } });
    }
 
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        r[i] = 1;
    }
 
    long long ans = 0;
    int cnt = 0;
    while (!q.empty())
    {
        long long w = -q.top().first;
        int x = q.top().second.first;
        int y = q.top().second.second;
        q.pop();
 
        if (find(x) == find(y))
        {
            continue;
        }
 
        merge(x, y);
        ans += (-w);
        cnt++;
 
        if (cnt == n - 1)
        {
            break;
        }
    }
 
    printf("%lld\n", -ans);
 
 
 
    return 0;
}