Truyền Tin Khắp Nơi
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng gồm N đỉnh và M cạnh. Xây dựng đồ thị rút gọn (condensation graph). Hãy đếm số đỉnh trong đồ thị rút gọn có bậc vào bằng 0. Đây chính là số nguồn tin tối thiểu cần để truyền tin đến tất cả các đỉnh.
Nếu đồ thị đã liên thông mạnh (chỉ có 1 SCC), in 1.
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
- M dòng tiếp theo: u v
Dữ liệu ra
- Một số nguyên: số nguồn tin tối thiểu.
Ví dụ
| Input | Output |
|---|---|
| 6 7\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3 4 | 1 |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
Community Discussion