최소 스패닝 트리 (MST)

스패닝 트리 : 모든 정점 포함, 순환 X
최소 스패닝 트리 : 가중치의 합을 최소로 만드는 스패닝 트리

이를 위해, 크루스칼 알고리즘, 프림 알고리즘 등이 존재

크루스칼 알고리즘.

1) 간선의 가중치를 오름차순으로 정렬
2) 가중치가 가장 작은 간선을 선택.
3) 2개의 노드가 연결 되지 않았다면 서로 연결.

23743 방탈출

최소 스패닝 트리를 구하는 것으로 재해석 할 수 있다.
워프를 간선으로, 각 방을 노드로, 그리고 비상 탈출구를 하나의 노드로 생각할 수 있기 때문.

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

typedef struct _tempp
{
    int src;
    int des;
    int cost;
} Gr;
vector<Gr> ggraph[200002];
vector<Gr> edges;
bool compare(Gr a, Gr b)
{
    return a.cost < b.cost;
}
int parent[200003];
int find_parent(int x)
{
    if (parent[x] == x)
        return x;
    else
        return parent[x] = find_parent(parent[x]);
}
void uunion(int x, int y)
{
    x = find_parent(x);
    y = find_parent(y);
    if (x != y)
    {
        parent[y] = x;
    }
}
bool sameparent(int x, int y)
{
    x = find_parent(x);
    y = find_parent(y);
    if (x == y)
        return true;
    else
        return false;
}

int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= 200002; i++)
    {
        parent[i] = i;
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        ggraph[a].push_back(Gr{a, b, c});
        ggraph[b].push_back(Gr{b, a, c});
        edges.push_back(Gr{a, b, c});
    }

    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        ggraph[200001].push_back(Gr{200001, i + 1, temp});
        ggraph[i + 1].push_back(Gr{i + 1, 200001, temp});
        edges.push_back(Gr{200002, i + 1, temp});
    }
    sort(edges.begin(), edges.end(), compare);
    int sum = 0;
    for (int i = 0; i < edges.size(); i++)
    {
        if (sameparent(edges[i].src, edges[i].des) == false)
        {
            uunion(edges[i].src, edges[i].des);
            sum += edges[i].cost;
        }
    }
    cout << sum;
    return (0);
}