Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MESSAGE - Truyền tin |
Một lớp gồm N học sinh, mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều : u có thể gửi tin tới v nhưng v thì chưa chắc đã có thể gửi tin tới u).
Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả các học sinh. Để tiết kiệm thời gian, thầy chỉ nhắn tin tới 1 số học sinh rồi sau đó nhờ các học sinh này nhắn lại cho tất cả các bạn mà các học sinh đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho tất cả các học sinh trong lớp đều nhận được tin .
Hãy tìm một số ít nhất các học sinh mà thầy chủ nhiệm cần nhắn.
Input
- Dòng đầu là N, M (N <= 800, M là số lượng liên lạc 1 chiều)
- Một số dòng tiếp theo mỗi dòng gồm 2 số u , v cho biết học sinh u có thể gửi tin tới học sinh v
Output
- Gồm 1 dòng ghi số học sinh cần thầy nhắn tin.
Example
Input: 12 15 1 3 3 6 6 1 6 8 8 12 12 9 9 6 2 4 4 5 5 2 4 6 7 10 10 11 11 7 10 9 Output: 2Chọn các học sinh 7 và 2.
Được gửi lên bởi: | Nguyen Dinh Tu |
Ngày: | 2006-09-09 |
Thời gian chạy: | 0.100s |
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
|
|||||||||||
2012-11-22 09:45:44 Việt Hùng
Tim thành phần liên thông của các thành phần liên thông mạnh, mất nguyên một buổi chiều :( |
|||||||||||
2012-11-08 10:20:40 ðẹp trai bẩm sinh
tarjan tìm tplt mạnh :) |
|||||||||||
2012-09-15 11:25:02 Zer0 Kull
làm bằng DFS mà chạy tới test 9 thì báo kết quả sai |
|||||||||||
2011-12-24 07:30:01 tran tan
Last edit: 2011-12-24 07:42:01 |
|||||||||||
2011-12-24 07:29:29 tran tan
Last edit: 2011-12-24 07:30:50 |
|||||||||||
2011-11-30 01:22:40 thanhphuc
cai nay dung dfs thoi ltm la sai do |
|||||||||||
2011-11-07 09:08:56 thanhphuc
lam lien thong amnh la sai chac la dung dfs thoi |
|||||||||||
2011-11-07 09:08:15 thanhphuc
bai nay dau phai la lien thong manh dau |
|||||||||||
2011-11-05 16:04:17 voj
Chỉ tìm các thành phần liên thông mạnh? Giả sử có 2 thành phần liên thông mạnh thì cần nhắn tin đến 2 HS? |