kruskal.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include<sstream>
#include<list>
#include<iomanip>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <bitset>
#include <cassert>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
const int INF = 1000000000;
const long long LINF = 3e18 + 7;
const int MAX_N = 50010;
const int MAX_W = 1000010;
const int MAX_ARRAYK = 100000;
double PI = 3.14159265358979323846;
//using ll = long long;




// kruskal
struct edge { long long u, v; long long cost; };
long long V, E;
edge es[MAX_W];
long long par[MAX_N];
long long rank1[MAX_N];
long long siz[MAX_N];

void init(long long n) {
	for (long long i = 0; i < n; i++) {
		par[i] = i;
		rank1[i] = 0;
		siz[i] = 1;
	}
}

long long find(long long x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

void unite(long long x, long long y) {
	x = find(x);
	y = find(y);
	if (x == y) return;

	if (rank1[x] < rank1[y]) {
		par[x] = y;
		siz[y] += siz[x];
	}
	else {
		par[y] = x;
		siz[x] += siz[y];
		if (rank1[x] == rank1[y]) rank1[x]++;
	}
}

bool same(long long x, long long y) {
	return find(x) == find(y);
}

long long usize(long long x) {
	return siz[find(x)];
}

bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

long long kruskal() {
	sort(es, es + E, comp);
	init(V);
	long long res = 0;
	for (long long i = 0; i < E; i++) {
		edge e = es[i];
		if (!same(e.u, e.v)) {
			unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}




int main() {

	cin >> V >> E;
	for (long long e = 0; e < E; e++) {
		long long u, v, cost;
		cin >> u >> v >> cost;
		u--;
		v--;
		es[e].u = u;
		es[e].v = v;
		es[e].cost = cost;
	}

	cout << kruskal() << endl;

	return 0;
}