Thành Phần Liên Thông Mạnh
Xem dưới dạng PDF
Gửi bài giải
Điểm:
30
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Kiểu bài tập
Trang trại nuôi trồng thủy sản thông minh của Tèo gồm \(N\) ao nuôi và \(M\) kênh dẫn nước một chiều nối giữa các ao.
Một nhóm các ao nuôi được gọi là một "hệ tuần hoàn kín" nếu nước có thể chảy luân chuyển qua lại giữa bất kỳ cặp ao nào trong nhóm (trực tiếp hoặc gián tiếp). Tèo muốn đếm số lượng hệ tuần hoàn kín độc lập tối đại (Thành phần liên thông mạnh - SCC) trong trang trại của mình.
Định dạng đầu vào
- Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
- \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả kênh nước một chiều từ ao \(u\) sang ao \(v\).
Định dạng đầu ra
- Một số nguyên duy nhất là số lượng hệ tuần hoàn kín độc lập tối đại.
Ví dụ
Input:
4 4
1 2
2 3
3 1
3 4
Output:
2
Nhận xét