Алгоритм Краскала

import random

def leader(h):
    if P[h] != h:
        P[h] = leader(P[h])
    return P[h]

def unite(a, b):
    a = leader(a)
    b = leader(b)
    if random.randint(0, 1):
        a, b = b, a
    if a != b:
        P[a] = b

n, m = map(int, input().split())
P = list(range(n))
G = []

for _ in range(m):
    a, b, w = map(int, input().split())
    G.append([w, [a - 1, b - 1]])

cost = 0
G.sort()

for i in range(m):
    a = G[i][1][0]
    b = G[i][1][1]
    w = G[i][0]
    if leader(a) != leader(b):
        cost += w
        unite(a, b)

print(cost)

#include <bits/stdc++.h>
using namespace std;

vector<int> P;

int leader(int h) {
    if (P[h] != h) {
        P[h] = leader(P[h]);
    }
    return P[h];
}

void unite(int a, int b) {
    a = leader(a);
    b = leader(b);
    if (rand() % 2) {
        swap(a, b);
    }
    if (a != b) {
        P[a] = b;
    }
}

int main() {
    srand(time(0));
    
    int n, m;
    cin >> n >> m;
    
    P.resize(n);
    for (int i = 0; i < n; i++) {
        P[i] = i;
    }
    
    vector<tuple<int, int, int>> G;
    
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        G.push_back({w, a, b});
    }
    
    sort(G.begin(), G.end());
    
    int cost = 0;
    for (auto [w, a, b] : G) {
        if (leader(a) != leader(b)) {
            cost += w;
            unite(a, b);
        }
    }
    
    cout << cost << endl;
    
    return 0;
}