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

Không có ý kiến tại thời điểm này.