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

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