Số cạnh rừng khung nhỏ nhất

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

Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh và $M$ cạnh (có thể không liên thông). Một rừng khung nhỏ nhất (Minimum Spanning Forest) là tập hợp các cây khung nhỏ nhất trên từng thành phần liên thông.

Hãy tính số lượng cạnh có trong rừng khung nhỏ nhất của đồ thị.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
Dữ liệu ra
  • In ra một số nguyên là số cạnh trong rừng khung nhỏ nhất.
Ví dụ
Input Output
5 4
1 2 3
2 3 4
1 3 5
4 5 2
3
3 0 0
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \cdot 10^5$
Draft saved