Tìm Đỉnh An Toàn

Xem dưới dạng PDF

Gửi bài giải


Điểm: 20
Giới hạn thời gian: 1.5s
Giới hạn bộ nhớ: 256M
đầu vào: stdin
Đầu ra: stdout

Tác giả:
Kiểu bài tập

Tèo sở hữu danh mục đầu tư xoay vòng gồm \(N\) mã cổ phiếu liên kết. Dòng tiền dịch chuyển giữa các mã cổ phiếu được mô tả bằng đồ thị có hướng \(M\) cạnh.

Một mã cổ phiếu được xem là an toàn nếu từ mã đó, bất kể dòng tiền dịch chuyển như thế nào, ta chắc chắn sẽ kết thúc ở một mã cổ phiếu cụt (terminal node - mã không có dòng tiền dịch chuyển đi ra) và không bao giờ bị cuốn vào một vòng lặp vô hạn.

Hãy giúp Tèo tìm tất cả các mã cổ phiếu an toàn và sắp xếp chúng theo thứ tự tăng dần.

Đị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\) thể hiện dòng tiền chuyển từ cổ phiếu \(u\) sang cổ phiếu \(v\).

Định dạng đầu ra

  • Danh sách các mã cổ phiếu an toàn theo thứ tự tăng dần cách nhau bởi dấu cách.

Ví dụ

Input:

4 4
1 2
2 3
3 1
3 4

Output:

4

Nhận xét

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