Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
NUMBER - Biến đổi số |
Cho M máy biến đổi số được đánh số từ 1 đến M và 1 số nguyên dương N. Hoạt động của máy i được xác định bởi cặp số nguyên dương (ai,bi) (1<=ai,bi<=N). Máy nhận đầu vào là số nguyên dương ai và trả lại ở đầu ra số nguyên dương bi.
Ta nói một số nguyên dương X có thể biến đổi thành số nguyên dương Y nếu hoặc X=Y hoặc tồn tại dãy hữu hạn các số nguyên dương X= P1,P2,...,Pk =Y sao cho đối với 2 phần tử liên tiếp Pi và Pi+1 bất kỳ trong dãy, luôn tìm được 1 trong số các máy đã cho để biến đổi Pi thành Pi+1
Cho trước 1 số nguyên dương T (T<=N). Hãy bổ sung thêm 1 số ít nhất các máy biến đổi số để bất kì số nguyên dương nào từ 1 đến N đều có thể biến đổi thành T
Input
- Dòng 1: 3 số nguyên dương N, M, T (1<=N,M,T<=10^4)
- M dòng tiếp theo mỗi dòng chứa 1 cặp số tương ứng với một máy biến đổi số. Các số trên một dòng cách nhau bởi 1 dấu cách
Output
Ghi ra 1 dòng duy nhất chứa 1 số nguyên dương là số lượng máy biến đổi số cần thêm
Example
Input: 6 4 5 1 3 2 3 4 5 6 5 Output: 1
Được gửi lên bởi: | sieunhan |
Ngày: | 2008-12-14 |
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: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
hide comments
|
|||||||
2017-07-18 03:02:37
1 đấm AC |
|||||||
2016-12-21 02:17:44
liệt kê các TPLT yếu với khi liệt kê tới t thì không tính cung đi ra đúng không nhỉ Last edit: 2016-12-21 02:20:29 |
|||||||
2016-10-20 18:23:18
đơn giản là tạo dag mà sao mk ko ac nhỉ nản |
|||||||
2015-10-02 03:14:17
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/06/bien-doi-so-number/ |
|||||||
2015-09-28 18:11:54 Lollipop
Last edit: 2015-09-28 18:23:16 |
|||||||
2015-09-08 14:11:44
https://thewizard6296.wordpress.com/2015/09/04/5/ |
|||||||
2014-12-18 22:22:49 Sơn Tùng M-TP
xét xem có những nút nào tới được nút T. rồi từ những nút đó đi tìm những nút trung tâm thôi. :v |
|||||||
2014-08-28 12:03:13 SunShine.Smile
Bạn nào AC bài này rồi cho mình hỏi hướng làm với! |
|||||||
2014-06-29 07:04:55 Xiao Lang
Bài này tìm TPLT, xây lại đồ thị là đc Last edit: 2014-06-29 07:23:53 |
|||||||
2014-03-02 16:38:06 Lê Quang Hải
DFS thôi |