최소 스패닝트리(MST) - 크루스칼

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.

프림, 크루스칼이 있는데 둘중 하나만 알아도 된다 해서 일단은 그러는 중이다.

 

싸이클이 생기는지 알기 위해서 유니온 파인드를 활용한다.

 

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

베이스는 이 문제이다.

 

 

#include <iostream>
#define pii pair<int, int>
using namespace std;
 
class Edge
{
public :
    int start, end, dist;
};
 
 
Edge edge[100000];
int e_size = 0;
int parent[10001];
 
void q_sort(int left, int right)
{
    if (left >= right)
        return;
 
    swap(edge[left], edge[(left + right) / 2]);
 
    int i = left + 1; int j = right;
    int pivot = left;
 
    while (1)
    {
        while (i <= right && edge[i].dist < edge[pivot].dist)
            i++;
        while (j >= left + 1 && edge[j].dist > edge[pivot].dist)
            j--;
 
        if (i < j)
            swap(edge[i++], edge[j--]);
        else
            break;
    }
 
    swap(edge[pivot], edge[j]);
 
    q_sort(left, j - 1);
    q_sort(j + 1, right);
}
 
int find(int node)
{
    if (parent[node] == node)
        return node;
    return parent[node] = find(parent[node]);
}
 
int merge(Edge e)
{
    int a = find(e.start);
    int b = find(e.end);
 
    if (a == b)
        return 0;
    else
    {
        parent[a] = b;
        return e.dist;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int v, e;
    cin >> v >> e;
 
    int a, b, c;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b >> c;
        edge[e_size++] = { a,b,c };
 
    }
 
    q_sort(0, e - 1);
    
    for (int i = 1; i <= v; i++)
        parent[i] = i;
 
    int ans = 0;
    for (int i = 0; i < e_size; i++)
        ans += merge(edge[i]);
    
    cout << ans;
}