MST (Minimum Spanning Tree) - Kruskal Algorithm

코드

#include <stdio.h>
#include <tuple>
#include <vector>
#include <algorithm>

using namespace std;

typedef tuple<int, int, int> tpl;

int p[200001];

int find(int n) {
    if (p[n] < 0) return n;
    return p[n] = find(p[n]);
}

bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    p[a] = b;
    return true;
}

int solve(int m, int n)
{
    int i, x, y, z, ans = 0, cnt = 0, sum = 0;
    vector<tpl> e;
    for (i = 0; i < n; i++) {
        scanf("%d%d%d", &x, &y, &z);
        e.push_back(tpl(z, x, y));
        sum += z;
    }

    fill(p, p + m, -1);
    sort(e.begin(), e.end());

    for (tpl t : e) {
        if (merge(get<1>(t), get<2>(t))) {
            ans += get<0>(t);
            cnt++;
        }

        if (cnt == m - 1)
            break;
    }

    return sum - ans;
}

int main()
{
    int m, n;

    while (1) {
        scanf("%d%d", &m, &n);
        if (m == 0 && n == 0)
            break;
        printf("%d\n", solve(m, n));
    }

    return 0;
}

전력난 - https://www.acmicpc.net/problem/6497

정리

• 스패닝 트리
  • 무방향 그래프에서 간선을 뽑아서 만들 수 있는 트리
  • 따라서 스패닝트리의 노드는 V 개, 간선은 V-1 개로 구성된다.
• 최소 스패닝 트리
  • 간선에 가중치가 주어질 때, 간선의 합이 최소인 스패닝 트리를 말한다.
• 크루스칼 알고리즘 (Kruskal Algorithm)
  • 간선을 가중치 기준으로 오름차순 정렬한다.
  • 각 간선을 검토하는데, 양쪽 정점이 다른 집합인 경우 연결한다.
  • V-1개의 간선이 선택되면 MST 이다.
• 시간복잡도
  • O(ElogE) = O(ElogE) + O(Elog*V) // 정렬 + (union/find * E)

관련 문제

• 1922 : 네트워크 연결
• 6497 : Dark roads
• 1647 : 도시 분할 계획
• 4386 : Freckles
• 4343 : Arctic Network
• 2887 : 행성 터널 ★
• 1944 : 복제 로봇 ★
• 9373 : 복도 뚫기 ★

참고 자료

• 내용