THỰC HÀNH

Với đồ thị G = (V, E) ta xây dựng đồ thị mới G' = (E, V') cũng gồm các đỉnh của V nhưng các cạnh thì được xây dựng như sau:

Giữa 2 đỉnh u, v của G' có cạnh nối <=> có đường đi từ u đến v trong G. Đồ thị G' = (E, V') gọi là bao đóng của đồ thị G = (V, E).

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

Dữ liệu vào:

·         Dòng đầu chứa số nguyên n là số đỉnh của đồ thị G.

·         n dòng tiếp theo, dòng thứ ghi n số nguyên 0 hoặc 1 là dòng i của ma trận kề A.

Dữ liệu ra:

·         Ghi ra ma trận kề A’ của đồ thị G’ = (E, V’).

Ví dụ:

Giới hạn: 1 £n £100. 

Với đồ thị G = (V, E) ta xây dựng đồ thị mới G' = (E, V') cũng gồm các đỉnh của V nhưng các cạnh thì được xây dựng như sau:

Giữa 2 đỉnh u, v của G' có cạnh nối <=> có đường đi từ u đến v trong G. Đồ thị G' = (E, V') gọi là bao đóng của đồ thị G = (V, E).

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

Dữ liệu vào:

·         Dòng đầu chứa số nguyên n là số đỉnh của đồ thị G.

·         n dòng tiếp theo, dòng thứ ghi n số nguyên 0 hoặc 1 là dòng i của ma trận kề A.

Dữ liệu ra:

·         Ghi ra ma trận kề A’ của đồ thị G’ = (E, V’).

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: 1 £ n £ 100.