Tìm TPLT mạnh
Xem dạng PDF
Gửi bài giải
Điểm:
0,02 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho đồ thị G~(V~, ~E)~ có hướng ~N~ ~(1 \le N \le 10^{4})~ đỉnh ~M~ ~(1 \le M \le 10^{5})~ cung, Hãy đếm số thành phần liên thông mạnh của ~G~.
Input
Dòng đầu tiên là ~N~, ~M~.
~M~ dòng tiếp theo mô tả một cung của ~G~.
Output
Gồm một dòng duy nhất là số TPLT mạnh.
Sample Input 1
3 2
1 2
2 3
Sample Output 1
3
Sample Input 2
3 3
1 2
2 3
3 1
Sample Output 2
1
Note
Các bạn có thể tham khảo thuật toán ở đây: Tarjan Algorithm
Bình luận
ước up vote
xin up vote đi mà ae
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
có bộ test kh a mik xin dc kh a.
Các bạn để ý không kiểm tra par[u]!=v như đối với đồ thị vô hướng khi chạy dfs nhé.
Có trường hợp:
2 2
1 2
2 1
Là nếu kiểm tra sẽ bị sai kết quả.
Test của bài tập này đã được cập nhật, cám ơn bạn lto5 đã đóng góp.