#538. COMPCONN – Thành phần liên thông

Đồ thị vô hướng được gọi là liên thông (connected) nếu giữa mọi cặp đỉnh của luôn tồn tại đường đi. Ví dụ hình dưới đây là một đồ thị liên thông.

Cho đồ thị vô hướng , là một tập con của . Ta nói là một thành phần liên thông của nếu hạn chế của trên tập là một đồ thị liên thông. Ví dụ hình dưới đây là đồ thị có thành phần liên thông.

Bài toán: Cho đơn đồ thị vô hướng có đỉnh và cạnh. Hãy tìm các thành phần liên thông của .

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên và là số đỉnh và số cạnh của đồ thị ;
• dòng tiếp theo, mỗi dòng chứa một cặp số cho biết một cạnh liên thuộc giữa và trong .

Dữ liệu ra:

• Dòng đầu ghi số nguyên dương là số thành phần liên thông trong ;
• dòng tiếp theo, mỗi dòng ghi một thành phần liên thông theo khuôn dạng: Số đầu là số đỉnh của thành phần liên thông, số tiếp theo là danh sách các đỉnh liệt kê theo thứ tự tăng dần.

Hai số trên cùng một dòng được ghi cách nhau một dấu cách, các thành phần liên thông liệt kê theo thứ tự các đỉnh nhỏ nhất tăng dần.

Ví dụ:

Dữ liệu:

7 6
1 2
1 3
2 3
5 6
6 7
5 7

Kết quả:

3
3 1 2 3
1 4
3 5 6 7

Dữ liệu:

12 10
10 7
10 11
1 4
5 4
5 6
2 3
2 12
12 3
3 8
12 9

Kết quả:

3
4 1 4 5 6
5 2 3 8 9 12
3 7 10 11

Giới hạn:

• .