1076.安全网络 ver.3

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge {
    edge() {}
    edge(int u, int v, int len) {
        this->u = u;
        this->v = v;
        this->len = len;
    }
    int u;
    int v;
    int len;
} e[200000];

int p[100001];
int r[100001];
int n, m;

int find(int u) {
    int y = u;
    int z = u;
    int w;
    while (p[y] != 0)
        y = p[y];
    while (p[z] != 0) {
        w = p[z];
        p[z] = y;
        z = w;
    }
    return y;
}

void unio(int u, int v) {
    if (r[u] >= r[v]) {
        p[v] = u;
        if (r[u] == r[v])
            r[u]++;
        return;
    }
    p[u] = v;
}

bool comp(edge e0, edge e1) {
    return e0.len < e1.len;
}

int kruskal() {
    int i, u, v, len = 0, nr = 0;
    sort(e, e + m, comp);
    for (i = 0; i < m; i++) {
        u = find(e[i].u);
        v = find(e[i].v);
        if (u != v) {
            len += e[i].len;
            nr++;
            if (nr == n - 1)
                return len;
            unio(u, v);
        }
    }
    return -1;
}

int main(int argc, char* argv[]) {
    int i;

    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++)
        scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].len);

    printf("%d\n", kruskal());

    return 0;
}