Kiểm tra liên thông
Points
8
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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
YESnếu đồ thị liên thông, ngược lại in raNO.
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$
Community Discussion