Số cụm nguồn trong đồ thị có hướng
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị có hướng gồm $N$ đỉnh và $M$ cung. Nếu ta co mỗi thành phần liên thông mạnh (SCC) thành một đỉnh duy nhất để tạo thành đồ thị có hướng không chu trình (DAG), hãy đếm số lượng đỉnh trên DAG này có bậc vào bằng $0$ (tức là các cụm nguồn tối thiểu cần truyền tin để phủ toàn bộ đồ thị).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ biểu thị một cung từ $u$ đến $v$.
Dữ liệu ra
- In ra một số nguyên duy nhất là số cụm nguồn (SCC có bậc vào bằng $0$).
Ví dụ
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 5 5 1 2 2 3 3 1 3 4 5 4 |
2 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
Community Discussion