Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HBAODONG - Bao đóng

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).

BAODONG

 

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=(aij). 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 £ 1000. 

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=(aij). 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 ££100. 

Ngôn ngữ

Kích thước mã ngồn

Thời gian

Bộ nhớ

C, C++, FPC, Java, Python

50000b

1s

128MB

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).

BAODONG

 

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=(aij). 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. 

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=(aij). 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 ££100. 

Ngôn ngữ

Kích thước mã ngồn

Thời gian

Bộ nhớ

C, C++, FPC, Java, Python

50000b

1s

128MB


Được gửi lên bởi:noname00.pas
Ngày:2017-10-22
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.