Kruskal

QBMST - Cây khung nhỏ nhất ( HEAP )

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbmst

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G

Input

Dòng 1: Chứa hai số n, m (1 <= n <= 10000; 1 <= m <= 15000)

M dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (1 <= u, v <= n; 0 <= c <= 10000).

Output

Gồm 1 dòng duy nhất: Ghi trọng số cây khung nhỏ nhất

Example

Input:
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2

Output:
5

 Submit solution!

CODE ACCEPTED

#include<bits/stdc++.h>
#define N 1000111
#define X first
#define Y second
#define int long long
using namespace std;

int vertex, edge, parent[N];
struct uvc{
	int u, v, c;
};
uvc a[N];

bool smaller(uvc x, uvc y){
	return x.c < y.c;
}

int root_replace(int u){
	if (parent[u] == u) return u;
	return parent[u]= root_replace(parent[u]);
}

void unify(int u, int v){
	parent[u]= v;
}

void kruskal(){
	sort(a+1, a+1+edge, smaller);
	
	for(int i=1; i<=vertex; i++) parent[i]= i;
	
	int s= 0, cnt= 0;
	for(int i=1; i<=edge; i++){
		
		int u= root_replace(a[i].u);
		int v= root_replace(a[i].v); 
		
		if (u != v){
			
			unify(u, v);
			s += a[i].c;
			
			if (++cnt==vertex-1) break;
		}
	}
	cout<<s;
}

int32_t main(){
	
	cin >> vertex >> edge;
	for(int i=1; i<=edge; i++)
		cin >> a[i].u >> a[i].v >> a[i].c;
	
	
	kruskal();
		
		
}