💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Phân Loại Cạnh MST
MST06
## Đề bài Cho đồ thị vô hướng liên thông. Với mỗi cạnh theo đúng thứ tự nhập, hãy phân loại: - `2` — **critical**: cạnh thuộc mọi cây khung nhỏ nhất. - `1` — **pseudo-critical**: cạnh thuộc ít nhất một nhưng không thuộc mọi cây khung nhỏ nhất. - `0` — **none**: cạnh không thuộc cây khung nhỏ nhất nào. ## Dữ liệu vào - Dòng đầu chứa `n`, `m`. - `m` dòng sau chứa `u`, `v`, `w`. ## Dữ liệu ra In `m` số `0`, `1`, `2` trên một dòng theo thứ tự cạnh ban đầu. ## Ràng buộc - `2 ≤ n ≤ 200000` - `n-1 ≤ m ≤ 400000` - `1 ≤ w ≤ 10^9` - Đồ thị liên thông, không có cạnh khuyên; cạnh song song được phép. ## Subtask - Subtask 1 (20%): `n ≤ 8`, có thể liệt kê tất cả MST. - Subtask 2 (30%): mọi trọng số đôi một khác nhau. - Subtask 3 (50%): không có ràng buộc thêm. ## Ví dụ ```text 4 5 1 2 1 2 3 1 1 3 1 3 4 2 1 4 5 ``` ```text 1 1 1 2 0 ``` ## Giải thích ví dụ Ba cạnh của tam giác có thể thay thế nhau; cạnh `3-4` bắt buộc; cạnh `1-4` quá nặng.
✅ Đã AC: 0 / 0 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng