Truyền tin

View as PDF
Submit solution
Points: 0.10 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 \le 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.

Sample 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

Sample Output

2

Note

Chọn các học sinh ~7~ và ~2~.

Comments

Please read the guidelines before commenting.


  • -10
    tboros2  commented on July 28, 2024, 11:50 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 11
      hh123123  commented on July 28, 2024, 12:44 p.m.

      test yếu vậy mà bạn còn không AC :(


  • -25
    xuanquang  commented on Sept. 16, 2023, 1:52 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -154
    thefrog  commented on Nov. 10, 2021, 1:40 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.