Truyền tin

Xem dạng PDF
Gửi bài giải
Điểm: 0,10 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
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~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    dangthithuhien0503  đã bình luận lúc 9, Tháng 4, 2025, 8:22

    ai chỉ mình cách làm bài này đc k ạ!


    • 5
      Groot  đã bình luận lúc 20, Tháng 7, 2025, 21:37

      Bạn gom nhóm đỉnh trong thành phần liên thông mạnh (SCC) của nó lại (xác định những đỉnh nào thuộc SCC đang xét). Sau khi gom nhóm sẽ ra 1 đồ thị rút gọn, tại sao lại gom nhóm? vì trong SCC chỉ cần 1 đứa nhận tin thì tin sẽ lan truyền với các đứa khác trong nhóm.

      Sau đó xét bậc vào của các nhóm (nhóm nào nối với nhóm nào). Các nhóm có bậc vào (degin > 0) thì đương nhiên sẽ được lan truyền bởi các nhóm khác nối vào nó --> Bài toán quay về đếm các nhóm không có bậc vào (degin == 0), vì ko có bậc vào thì mình buộc phải nhắn với nó để nó lan truyền đến các nhóm khác (hoặc không) :v


  • -24
    phanthedan2009  đã bình luận lúc 14, Tháng 2, 2025, 7:53 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -22
    tboros2  đã bình luận lúc 28, Tháng 7, 2024, 11:50

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 16
      hh123123  đã bình luận lúc 28, Tháng 7, 2024, 12:44

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


      • 2
        truonghovuviet  đã bình luận lúc 25, Tháng 1, 2025, 3:38

        Bài này dfs test yếu mới AC à bạn


  • -30
    xuanquang  đã bình luận lúc 16, Tháng 9, 2023, 1:52 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -170
    thefrog  đã bình luận lúc 10, Tháng 11, 2021, 13:40

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.