Cây khung nhỏ nhất và danh sách cạnh

Buổi 20 — Cây khung nhỏ nhất
Points
15
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 đánh số từ $1$ đến $M$. Hãy tìm cây khung nhỏ nhất bằng thuật toán Kruskal. Khi hai cạnh có cùng trọng số, hãy ưu tiên chọn cạnh có chỉ số nhỏ hơn.

Nếu đồ thị liên thông, hãy in ra tổng trọng số của cây khung nhỏ nhất và danh sách chỉ số các cạnh được chọn theo thứ tự tăng dần. Ngược lại, in ra -1.

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, dòng thứ $i$ 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
  • Nếu đồ thị không liên thông, in ra -1.
  • Ngược lại, dòng đầu in tổng trọng số MST. Dòng thứ hai in $N-1$ chỉ số cạnh được chọn theo thứ tự tăng dần, cách nhau bởi dấu cách (nếu $N=1$, dòng thứ hai để trống).
Ví dụ
Input Output
4 5
1 2 2
2 3 2
3 4 2
1 4 2
1 3 5
6
1 2 3
3 1
1 2 10
-1
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \cdot 10^5$
  • $1 \le w_i \le 10^9$
Draft saved