Đếm Thành Phố Liên Kết
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng gồm N đỉnh và M cạnh. Hãy đếm số thành phần liên thông mạnh (SCC) của đồ thị.
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
- M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v, mô tả cạnh có hướng từ u đến v (1 ≤ u, v ≤ N)
Dữ liệu ra
- Một số nguyên duy nhất: số thành phần liên thông mạnh của đồ thị.
Ví dụ
| Input | Output |
|---|---|
| 5 5\n1 2\n2 3\n3 1\n4 5\n5 4 | 3 |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
Community Discussion