최소 스패닝 트리(MST)와 크루스칼 알고리즘

정점: 1, 2, 3, 4, 5, 6
간선 목록 (가중치 오름차순 정렬):
(1-5): 1
(4-5): 2
(1-4): 3  ← 사이클 발생 → 스킵
(1-3): 4
(2-4): 4
(2-5): 5
(3-6): 6
(4-6): 8
(1-2): 9

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False  # 사이클 발생
    parent[ry] = rx
    return True

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False  # 사이클 발생 → 스킵
    if rx < ry:
        parent[ry] = rx
    else:
        parent[rx] = ry
    return True

def kruskal(v, edges):
    global parent
    parent = list(range(v + 1))

    # 간선을 가중치 기준 오름차순 정렬
    edges.sort(key=lambda x: x[0])

    mst = []
    total_cost = 0

    for cost, a, b in edges:
        if union(a, b):  # 사이클이 없으면 MST에 추가
            mst.append((a, b, cost))
            total_cost += cost
        if len(mst) == v - 1:  # V-1개 선택 시 종료
            break

    return mst, total_cost


# 사용 예시
v = 6
edges = [
    (1, 1, 5),
    (4, 1, 3),
    (3, 1, 4),
    (9, 1, 2),
    (4, 2, 4),
    (5, 2, 5),
    (6, 3, 6),
    (2, 4, 5),
    (8, 4, 6),
]

mst, total = kruskal(v, edges)

print("[MST]")
for a, b, cost in mst:
    print(f"{a} - {b} : 비용 {cost}")
print(f"총 비용: {total}")

[MST]
1 - 5 : 비용 1
4 - 5 : 비용 2
1 - 4 : 비용 3  ← 사이클로 스킵됨 (실제 출력 안됨)
1 - 3 : 비용 4
2 - 4 : 비용 4
3 - 6 : 비용 6
총 비용: 17

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int, int>> Edge;

int parent[10001];

int find_root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);  // 경로 압축
}

bool union_root(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) return false;  // 사이클 발생
    if (x < y) parent[y] = x;
    else parent[x] = y;
    return true;
}

int main() {
    int v, e;
    cin >> v >> e;

    vector<Edge> edges;
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({c, {a, b}});
    }

    // 가중치 기준 오름차순 정렬
    sort(edges.begin(), edges.end());

    // Union-Find 초기화
    for (int i = 1; i <= v; i++) parent[i] = i;

    int total_cost = 0;
    int edge_count = 0;

    for (auto& edge : edges) {
        int cost = edge.first;
        int a = edge.second.first;
        int b = edge.second.second;

        if (union_root(a, b)) {
            total_cost += cost;
            edge_count++;
            cout << a << " - " << b << " : 비용 " << cost << "\n";
        }

        if (edge_count == v - 1) break;
    }

    cout << "총 비용: " << total_cost << "\n";
    return 0;
}