Kiểm tra liên thông

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

Cho một đồ thị vô hướng có trọng số gồm $N$ đỉnh và $M$ cạnh. Hãy sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) để kiểm tra xem đồ thị có liên thông hay không (tức là từ mọi đỉnh đều có thể đi đến mọi đỉnh khác).

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 YES nếu đồ thị liên thông, ngược lại in ra NO.
Ví dụ
Input Output
4 3
1 2 5
2 3 2
3 4 1
YES
4 3
1 2 5
2 3 2
1 3 1
NO
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \cdot 10^5$
Draft saved