Đồ thị có hướng được gọi là liên thông (strongly connected) nếu giữa mọi cặp đỉnh của luôn tồn tại đường đi (định hướng).
Cho đồ thị có hướng , là một tập con của . Ta nói là một thành phần liên thông mạnh của nếu hạn chế của trên tập : là một đồ thị liên thông mạnh.
Bài toán: Cho đồ thị có hướng có đỉnh và cung. Hãy tìm các thành phần liên thông mạnh của .
Dữ liệu vào:
Dòng đầu chứa hai số nguyên và là số đỉnh và số cung của đồ thị ;
dòng tiếp theo, mỗi dòng chứa một cặp số cho biết một cung nối từ tới trong .
Dữ liệu ra:
Dòng đầu ghi số nguyên dương là số thành phần liên thông mạnh trong ;
dòng tiếp theo, mỗi dòng ghi một thành phần liên thông mạnh theo khuôn dạng: Số đầu là số đỉnh của thành phần liên thông mạnh, số tiếp theo là danh sách các đỉnh của thành phần liên thông đó.
Hai số trên cùng một dòng được ghi cách nhau một dấu cách.
