#539. HBAODONG – Bao đóng (Bản khó)

Với đồ thị ta xây dựng đồ thị mới cũng gồm các đỉnh của nhưng các cạnh thì được xây dựng như sau: Giữa hai đỉnh của có cạnh nối có đường đi từ đến trong . Đồ thị gọi là bao đóng của đồ thị .

Bài toán: Cho đơn đồ thị có đỉnh được biểu diễn vởi ma trận kề . Hãy tìm bao đóng của .

Dữ liệu vào:

• Dòng đầu chứa số nguyên là số đỉnh của đồ thị ;
• dòng tiếp theo, dòng thứ ghi số nguyên hoặc là dòng của ma trận kề .

Dữ liệu ra:

• Ghi ra ma trận kề của đồ thị .

Ví dụ:

Dữ liệu vào:

5
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0

Dữ liệu ra:

0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Giới hạn:

• .