Thuật toán Kosaraju tìm thành phần liên thông mạnh (SCC)

Mục tiêu kiến thức

• Hiểu định nghĩa Thành phần liên thông mạnh (Strongly Connected Component - SCC) trên đồ thị có hướng.
• Nắm vững thuật toán Kosaraju-Sharir với 2 lượt duyệt DFS:
• Lượt 1: DFS trên đồ thị xuôi G để thu thập thứ tự topo theo thời điểm kết thúc (exit_time stack).
• Lượt 2: DFS trên đồ thị chuyển vị G^T theo thứ tự đỉnh từ đỉnh ngăn xếp lấy ra.
• Đạt độ phức tạp thời gian tuyến tính O(V + E).

Mô tả bài toán

Cho một đồ thị có hướng gồm N đỉnh (1 ≤ N ≤ 10⁵) và M cạnh (0 ≤ M ≤ 2 · 10⁵). Hãy đếm số lượng thành phần liên thông mạnh (SCC) của đồ thị.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 10⁵.
• 0 ≤ M ≤ 2 · 10⁵.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.