| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P156SUMB - ROUND 6B - Tìm đỉnh dốc |
Cho một đồ thị có hướng liên thông yếu gồm n đỉnh và n – 1 cạnh, các đỉnh được đánh số từ 1 đến n.
Một đỉnh được gọi là đỉnh dốc nếu như nó có đường đi tới tất cả các đỉnh còn lại. Nhiệm vụ của bạn là phải đảo chiều một số cạnh của đồ để được đồ thị mới có đỉnh dốc.
Input
Dòng đầu tiên chứa số n là số đỉnh của đồ thị (2 <= n <= 2*10^5).
n – 1 dòng sau, mỗi dòng gồm 2 số nguyên u, v, thể hiện cạnh u->v của đồ thị.
Output
Dòng đầu tiên in ra số lần đảo chiều nhỏ nhất với cách chọn đỉnh dốc tối ưu.
Dòng tiếp theo in ra các đỉnh dốc có thể có với số lần đảo như trên, theo thứ tự tăng dần.
Example
Input:8
1 2
3 2
4 3
4 5
6 5
6 7
8 7 Output:3
4 6 8
| Được gửi lên bởi: | adm |
| Ngày: | 2015-08-06 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
