Tính duy nhất của cây khung
Points
26
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh và $M$ cạnh. Hãy kiểm tra xem cây khung nhỏ nhất (MST) của đồ thị có duy nhất hay không (hai cây khung được coi là khác nhau nếu tập các chỉ số cạnh được chọn khác nhau).
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
DISCONNECTEDnếu đồ thị không liên thông. - In ra
UNIQUEnếu MST là duy nhất. - In ra
NOT UNIQUEnếu tồn tại ít nhất hai MST khác nhau.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 1 2 3 2 3 4 3 1 4 4 1 3 5 |
UNIQUE |
| 4 5 1 2 1 2 3 1 1 3 1 3 4 2 2 4 3 |
NOT UNIQUE |
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$
Community Discussion