Cây Khung Nhỏ Nhất (Kruskal & Disjoint Set Union)

Buổi 20 — Cây khung nhỏ nhất Graphs Trees
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị vô hướng liên thông gồm N đỉnh (1..N) và M cạnh có trọng số. Hãy tìm tổng trọng số của Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST) nối toàn bộ N đỉnh.

Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên N và M (1 ≤ N ≤ 10^5, N - 1 ≤ M ≤ 2 × 10^5).
  • M dòng tiếp theo: Mỗi dòng gồm 3 số nguyên u v w (1 ≤ w ≤ 10^9).
Dữ liệu ra (Output)
  • In ra tổng trọng số nhỏ nhất của cây khung.
Ví dụ mẫu
Sample Input 1
4 5
1 2 1
1 3 4
2 3 2
2 4 6
3 4 3
Sample Output 1
6
Draft saved