Tìm TPLT mạnh

View as PDF
Submit solution
Points: 0.11 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Bài cơ bản - tests added by canhteo
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 18
    hxano  commented on April 11, 2023, 4:32 p.m. ← edit 2

    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ả.


  • 29
    leduykhongngu  commented on Aug. 23, 2021, 9:27 a.m.

    Test của bài tập này đã được cập nhật, cám ơn bạn lto5 đã đóng góp.