Tìm TPLT mạnh
Xem dạng PDF
Gửi bài giải
Điểm:
0,11 (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ó 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.