#786. Những chú bò nổi tiếng (POPULAR)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Mỗi con bò đều có mong muốn trở thành con bò nổi tiếng nhất. Hiện có N con bò, cho M cặp số nguyên (A,B) , biểu thị con bò A cho rằng con bò B là nổi tiếng. Mối quan hệ này có tính chất bắc cầu: nếu A cho rằng B nổi tiếng, và B cho rằng C nổi tiếng, thì con bò A cũng sẽ cho rằng con bò C nổi tiếng. Nhiệm vụ của bạn là tìm ra có bao nhiêu con bò được tất cả các con bò khác (trừ chính nó) coi là nổi tiếng.

Dữ liệu:

  • Dòng đầu tiên chứa hai số N, M .
  • M dòng tiếp theo, mỗi dòng chứa hai số A, B , nghĩa là A cho rằng B nổi tiếng (thông tin có thể bị lặp lại).

Kết quả:

  • Xuất ra số lượng con bò được tất cả các con bò khác (trừ chính nó) coi là nổi tiếng.

Ví dụ:

Dữ liệu:

3 3
1 2
2 1
2 3

Kết quả:

1

Giới hạn: 1\le N\le 10^4, 1\le M\le 5\times 10^4 .