0466 - Gen Graf

Cerinţa

Se dă un număr natural n. Construiți toate grafurile neorientate cu n vârfuri.

Date de intrare

Fişierul de intrare gengrafIN.txt conţine pe prima linie numărul n.

Date de ieşire

Fişierul de ieşire gengrafOUT.txt va conţine pe prima linie numărul de grafuri generate M; urmează M matrice de adiacență ale acestor grafuri.

Fiecare matrice va fi afișată astfel: câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu. După fiecare matrice afișată se va găsi în fișier o linie goală.

Restricţii şi precizări

• 2 ≤ n ≤ 6
• cele M matrice de adiacență construite pot fi afișate în orice ordine

Exemplul 1

gengrafIN.txt:

3

gengrafOUT.txt:

8

0 0 0

0 0 0

0 0 0

0 1 0

1 0 0

0 0 0

0 0 1

0 0 0

1 0 0

0 1 1

1 0 0

1 0 0

0 0 0

0 0 1

0 1 0

0 1 0

1 0 1

0 1 0

0 0 1

0 0 1

1 1 0

0 1 1

1 0 1

1 1 0

Exemplul 2

gengrafIN.txt:

7

Output:

Valoarea lui n nu respectă restricția 2 <= n <= 6.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def generate_graphs(n):

   graphs = []
   for i in range(2**(n*(n-1)//2)):
       graph_matrix = [[0]*n for _ in range(n)]
       idx = 0
       for j in range(n):
           for k in range(j+1, n):
               graph_matrix[j][k] = graph_matrix[k][j] = (i >> idx) & 1
               idx += 1
       graphs.append(graph_matrix)
   return graphs

def write_to_file(graphs, filename):

   with open(filename, 'w') as file:
       file.write(str(len(graphs)) + '\n')
       for graph in graphs:
           for row in graph:
               file.write(' '.join(map(str, row)) + '\n')
           file.write('\n')

def check_n_range(n):

   return 2 <= n <= 6

if __name__ == "__main__":

   with open('gengrafIN.txt', 'r') as input_file:
       n = int(input_file.readline().strip())

   if check_n_range(n):
       graphs = generate_graphs(n)
       write_to_file(graphs, 'gengrafOUT.txt')
   else:
       print("Valoarea lui n nu respectă restricția 2 <= n <= 6.")

</syntaxhighlight>