VMST - Cây khung
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một đơn đồ thị liên thông gồm N đỉnh, M cạnh. Các đỉnh của đồ thị được đánh số từ 1 đến N. Tìm 3 cây khung khác nhau của đồ thị.
Định nghĩa cây khung của đồ thị:
Cây khung của đồ thị G gồm N đỉnh, M cạnh, là một đồ thị G’ gồm tất cả N đỉnh của đồ thị G, và đúng N-1 cạnh của đồ thị G, và G’ là đồ thị liên thông.
Input
Dòng đầu: 2 số nguyên dương N và M (1 < N <= M, N <= 1000, M <= 1500)
M dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u, v (u khác v) thể hiện 1 cạnh nối giữa u và v. Input đảm bảo đồ thị liên thông và có ít nhất 3 cây khung khác nhau.
Output
Dòng 1 gồm 1 số nguyên dương K duy nhất - số cây khung mà bạn tìm được (0 <= K <= 3).
Tiếp theo là K nhóm dòng, mỗi nhóm dòng gồm đúng N-1 dòng, thể hiện 1 cây khung.
Cách tính điểm
- Nếu trong K cây khung mà bạn tìm được, có một cây khung không hợp lệ (có chu trình, không liên thông), hoặc có 2 cây khung giống nhau thì bạn không được điểm nào
- Nếu K = 0, bạn không được điểm nào
- Nếu K = 1, bạn được 20% số điểm của test
- Nếu K = 2, bạn được 40% số điểm của test
- Nếu K = 3, bạn được 100% số điểm của test
Bài này có đúng 20 test, tổng điểm là 100. Trong lúc thi bạn chỉ được chấm với 2 test (không bao gồm test đề bài), và điểm tối đa mà bạn có thể nhận được là 10 điểm.
Example
Input: 3 3 1 2 2 3 3 1 Output: 3 1 2 2 3 2 3 3 1 3 1 1 2
- Người up: voj